/src/postgres/src/backend/utils/adt/arrayfuncs.c

Source
/*-------------------------------------------------------------------------
 *
 * arrayfuncs.c
 *    Support functions for arrays.
 *
 * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *    src/backend/utils/adt/arrayfuncs.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <ctype.h>
#include <math.h>

#include "access/transam.h"
#include "catalog/pg_type.h"
#include "common/int.h"
#include "funcapi.h"
#include "libpq/pqformat.h"
#include "nodes/nodeFuncs.h"
#include "nodes/supportnodes.h"
#include "optimizer/optimizer.h"
#include "parser/scansup.h"
#include "port/pg_bitutils.h"
#include "utils/array.h"
#include "utils/arrayaccess.h"
#include "utils/builtins.h"
#include "utils/datum.h"
#include "utils/fmgroids.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/selfuncs.h"
#include "utils/typcache.h"


/*
 * GUC parameter
 */
bool    Array_nulls = true;

/*
 * Local definitions
 */
#define ASSGN  "="

#define AARR_FREE_IF_COPY(array,n) \
  do { \
    if (!VARATT_IS_EXPANDED_HEADER(array)) \
      PG_FREE_IF_COPY(array, n); \
  } while (0)

/* ReadArrayToken return type */
typedef enum
{
  ATOK_LEVEL_START,
  ATOK_LEVEL_END,
  ATOK_DELIM,
  ATOK_ELEM,
  ATOK_ELEM_NULL,
  ATOK_ERROR,
} ArrayToken;

/* Working state for array_iterate() */
typedef struct ArrayIteratorData
{
  /* basic info about the array, set up during array_create_iterator() */
  ArrayType  *arr;      /* array we're iterating through */
  uint8    *nullbitmap;   /* its null bitmap, if any */
  int     nitems;     /* total number of elements in array */
  int16   typlen;     /* element type's length */
  bool    typbyval;   /* element type's byval property */
  char    typalign;   /* element type's align property */
  uint8   typalignby;   /* typalign mapped to numeric alignment */

  /* information about the requested slice size */
  int     slice_ndim;   /* slice dimension, or 0 if not slicing */
  int     slice_len;    /* number of elements per slice */
  int      *slice_dims;   /* slice dims array */
  int      *slice_lbound; /* slice lbound array */
  Datum    *slice_values; /* workspace of length slice_len */
  bool     *slice_nulls;  /* workspace of length slice_len */

  /* current position information, updated on each iteration */
  char     *data_ptr;   /* our current position in the array */
  int     current_item; /* the item # we're at in the array */
} ArrayIteratorData;

static bool ReadArrayDimensions(char **srcptr, int *ndim_p,
                int *dim, int *lBound,
                const char *origStr, Node *escontext);
static bool ReadDimensionInt(char **srcptr, int *result,
               const char *origStr, Node *escontext);
static bool ReadArrayStr(char **srcptr,
             FmgrInfo *inputproc, Oid typioparam, int32 typmod,
             char typdelim,
             int typlen, bool typbyval, char typalign,
             int *ndim_p, int *dim,
             int *nitems_p,
             Datum **values_p, bool **nulls_p,
             const char *origStr, Node *escontext);
static ArrayToken ReadArrayToken(char **srcptr, StringInfo elembuf, char typdelim,
                 const char *origStr, Node *escontext);
static void ReadArrayBinary(StringInfo buf, int nitems,
              FmgrInfo *receiveproc, Oid typioparam, int32 typmod,
              int typlen, bool typbyval, char typalign,
              Datum *values, bool *nulls,
              bool *hasnulls, int32 *nbytes);
static Datum array_get_element_expanded(Datum arraydatum,
                    int nSubscripts, int *indx,
                    int arraytyplen,
                    int elmlen, bool elmbyval, char elmalign,
                    bool *isNull);
static Datum array_set_element_expanded(Datum arraydatum,
                    int nSubscripts, int *indx,
                    Datum dataValue, bool isNull,
                    int arraytyplen,
                    int elmlen, bool elmbyval, char elmalign);
static bool array_get_isnull(const uint8 *nullbitmap, int offset);
static void array_set_isnull(uint8 *nullbitmap, int offset, bool isNull);
static Datum ArrayCast(char *value, bool byval, int len);
static int  ArrayCastAndSet(Datum src,
              int typlen, bool typbyval, uint8 typalignby,
              char *dest);
static char *array_seek(char *ptr, int offset, uint8 *nullbitmap, int nitems,
            int typlen, bool typbyval, char typalign);
static int  array_nelems_size(char *ptr, int offset, uint8 *nullbitmap,
                int nitems, int typlen, bool typbyval, char typalign);
static int  array_copy(char *destptr, int nitems,
             char *srcptr, int offset, uint8 *nullbitmap,
             int typlen, bool typbyval, char typalign);
static int  array_slice_size(char *arraydataptr, uint8 *arraynullsptr,
               int ndim, int *dim, int *lb,
               int *st, int *endp,
               int typlen, bool typbyval, char typalign);
static void array_extract_slice(ArrayType *newarray,
                int ndim, int *dim, int *lb,
                char *arraydataptr, uint8 *arraynullsptr,
                int *st, int *endp,
                int typlen, bool typbyval, char typalign);
static void array_insert_slice(ArrayType *destArray, ArrayType *origArray,
                 ArrayType *srcArray,
                 int ndim, int *dim, int *lb,
                 int *st, int *endp,
                 int typlen, bool typbyval, char typalign);
static int  array_cmp(FunctionCallInfo fcinfo);
static ArrayType *create_array_envelope(int ndims, int *dimv, int *lbsv, int nbytes,
                    Oid elmtype, int dataoffset);
static ArrayType *array_fill_internal(ArrayType *dims, ArrayType *lbs,
                    Datum value, bool isnull, Oid elmtype,
                    FunctionCallInfo fcinfo);
static ArrayType *array_replace_internal(ArrayType *array,
                     Datum search, bool search_isnull,
                     Datum replace, bool replace_isnull,
                     bool remove, Oid collation,
                     FunctionCallInfo fcinfo);
static int  width_bucket_array_float8(Datum operand, ArrayType *thresholds);
static int  width_bucket_array_fixed(Datum operand,
                   ArrayType *thresholds,
                   Oid collation,
                   TypeCacheEntry *typentry);
static int  width_bucket_array_variable(Datum operand,
                    ArrayType *thresholds,
                    Oid collation,
                    TypeCacheEntry *typentry);


/*
 * array_in :
 *      converts an array from the external format in "string" to
 *      its internal format.
 *
 * return value :
 *      the internal representation of the input array
 */
Datum
array_in(PG_FUNCTION_ARGS)
{
  char     *string = PG_GETARG_CSTRING(0);  /* external form */
  Oid     element_type = PG_GETARG_OID(1);  /* type of an array
                           * element */
  int32   typmod = PG_GETARG_INT32(2);  /* typmod for array elements */
  Node     *escontext = fcinfo->context;
  int     typlen;
  bool    typbyval;
  char    typalign;
  uint8   typalignby;
  char    typdelim;
  Oid     typioparam;
  char     *p;
  int     nitems;
  Datum    *values;
  bool     *nulls;
  bool    hasnulls;
  int32   nbytes;
  int32   dataoffset;
  ArrayType  *retval;
  int     ndim,
        dim[MAXDIM],
        lBound[MAXDIM];
  ArrayMetaState *my_extra;

  /*
   * We arrange to look up info about element type, including its input
   * conversion proc, 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 info about element type, including its input conversion proc
     */
    get_type_io_data(element_type, IOFunc_input,
             &my_extra->typlen, &my_extra->typbyval,
             &my_extra->typalign, &my_extra->typdelim,
             &my_extra->typioparam, &my_extra->typiofunc);
    fmgr_info_cxt(my_extra->typiofunc, &my_extra->proc,
            fcinfo->flinfo->fn_mcxt);
    my_extra->element_type = element_type;
  }
  typlen = my_extra->typlen;
  typbyval = my_extra->typbyval;
  typalign = my_extra->typalign;
  typalignby = typalign_to_alignby(typalign);
  typdelim = my_extra->typdelim;
  typioparam = my_extra->typioparam;

  /*
   * Initialize dim[] and lBound[] for ReadArrayStr, in case there is no
   * explicit dimension info.  (If there is, ReadArrayDimensions will
   * overwrite this.)
   */
  for (int i = 0; i < MAXDIM; i++)
  {
    dim[i] = -1;      /* indicates "not yet known" */
    lBound[i] = 1;      /* default lower bound */
  }

  /*
   * Start processing the input string.
   *
   * If the input string starts with dimension info, read and use that.
   * Otherwise, we'll determine the dimensions during ReadArrayStr.
   */
  p = string;
  if (!ReadArrayDimensions(&p, &ndim, dim, lBound, string, escontext))
    return (Datum) 0;

  if (ndim == 0)
  {
    /* No array dimensions, so next character should be a left brace */
    if (*p != '{')
      ereturn(escontext, (Datum) 0,
          (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
           errmsg("malformed array literal: \"%s\"", string),
           errdetail("Array value must start with \"{\" or dimension information.")));
  }
  else
  {
    /* If array dimensions are given, expect '=' operator */
    if (strncmp(p, ASSGN, strlen(ASSGN)) != 0)
      ereturn(escontext, (Datum) 0,
          (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
           errmsg("malformed array literal: \"%s\"", string),
           errdetail("Missing \"%s\" after array dimensions.",
                 ASSGN)));
    p += strlen(ASSGN);
    /* Allow whitespace after it */
    while (scanner_isspace(*p))
      p++;

    if (*p != '{')
      ereturn(escontext, (Datum) 0,
          (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
           errmsg("malformed array literal: \"%s\"", string),
           errdetail("Array contents must start with \"{\".")));
  }

  /* Parse the value part, in the curly braces: { ... } */
  if (!ReadArrayStr(&p,
            &my_extra->proc, typioparam, typmod,
            typdelim,
            typlen, typbyval, typalign,
            &ndim,
            dim,
            &nitems,
            &values, &nulls,
            string,
            escontext))
    return (Datum) 0;

  /* only whitespace is allowed after the closing brace */
  while (*p)
  {
    if (!scanner_isspace(*p++))
      ereturn(escontext, (Datum) 0,
          (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
           errmsg("malformed array literal: \"%s\"", string),
           errdetail("Junk after closing right brace.")));
  }

  /* Empty array? */
  if (nitems == 0)
    PG_RETURN_ARRAYTYPE_P(construct_empty_array(element_type));

  /*
   * Check for nulls, compute total data space needed
   */
  hasnulls = false;
  nbytes = 0;
  for (int i = 0; i < nitems; i++)
  {
    if (nulls[i])
      hasnulls = true;
    else
    {
      /* let's just make sure data is not toasted */
      if (typlen == -1)
        values[i] = PointerGetDatum(PG_DETOAST_DATUM(values[i]));
      nbytes = att_addlength_datum(nbytes, typlen, values[i]);
      nbytes = att_nominal_alignby(nbytes, typalignby);
      /* check for overflow of total request */
      if (!AllocSizeIsValid(nbytes))
        ereturn(escontext, (Datum) 0,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxAllocSize)));
    }
  }
  if (hasnulls)
  {
    dataoffset = ARR_OVERHEAD_WITHNULLS(ndim, nitems);
    nbytes += dataoffset;
  }
  else
  {
    dataoffset = 0;     /* marker for no null bitmap */
    nbytes += ARR_OVERHEAD_NONULLS(ndim);
  }

  /*
   * Construct the final array datum
   */
  retval = (ArrayType *) palloc0(nbytes);
  SET_VARSIZE(retval, nbytes);
  retval->ndim = ndim;
  retval->dataoffset = dataoffset;

  /*
   * This comes from the array's pg_type.typelem (which points to the base
   * data type's pg_type.oid) and stores system oids in user tables. This
   * oid must be preserved by binary upgrades.
   */
  retval->elemtype = element_type;
  memcpy(ARR_DIMS(retval), dim, ndim * sizeof(int));
  memcpy(ARR_LBOUND(retval), lBound, ndim * sizeof(int));

  CopyArrayEls(retval,
         values, nulls, nitems,
         typlen, typbyval, typalign,
         true);

  pfree(values);
  pfree(nulls);

  PG_RETURN_ARRAYTYPE_P(retval);
}

/*
 * ReadArrayDimensions
 *   parses the array dimensions part of the input and converts the values
 *   to internal format.
 *
 * On entry, *srcptr points to the string to parse. It is advanced to point
 * after whitespace (if any) and dimension info (if any).
 *
 * *ndim_p, dim[], and lBound[] are output variables. They are filled with the
 * number of dimensions (<= MAXDIM), the lengths of each dimension, and the
 * lower subscript bounds, respectively.  If no dimension info appears,
 * *ndim_p will be set to zero, and dim[] and lBound[] are unchanged.
 *
 * 'origStr' is the original input string, used only in error messages.
 * If *escontext points to an ErrorSaveContext, details of any error are
 * reported there.
 *
 * Result:
 *  true for success, false for failure (if escontext is provided).
 *
 * Note that dim[] and lBound[] are allocated by the caller, and must have
 * MAXDIM elements.
 */
static bool
ReadArrayDimensions(char **srcptr, int *ndim_p, int *dim, int *lBound,
          const char *origStr, Node *escontext)
{
  char     *p = *srcptr;
  int     ndim;

  /*
   * Dimension info takes the form of one or more [n] or [m:n] items.  This
   * loop iterates once per dimension item.
   */
  ndim = 0;
  for (;;)
  {
    char     *q;
    int     ub;
    int     i;

    /*
     * Note: we currently allow whitespace between, but not within,
     * dimension items.
     */
    while (scanner_isspace(*p))
      p++;
    if (*p != '[')
      break;       /* no more dimension items */
    p++;
    if (ndim >= MAXDIM)
      ereturn(escontext, false,
          (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
           errmsg("number of array dimensions exceeds the maximum allowed (%d)",
              MAXDIM)));

    q = p;
    if (!ReadDimensionInt(&p, &i, origStr, escontext))
      return false;
    if (p == q)       /* no digits? */
      ereturn(escontext, false,
          (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
           errmsg("malformed array literal: \"%s\"", origStr),
           errdetail("\"[\" must introduce explicitly-specified array dimensions.")));

    if (*p == ':')
    {
      /* [m:n] format */
      lBound[ndim] = i;
      p++;
      q = p;
      if (!ReadDimensionInt(&p, &ub, origStr, escontext))
        return false;
      if (p == q)     /* no digits? */
        ereturn(escontext, false,
            (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
             errmsg("malformed array literal: \"%s\"", origStr),
             errdetail("Missing array dimension value.")));
    }
    else
    {
      /* [n] format */
      lBound[ndim] = 1;
      ub = i;
    }
    if (*p != ']')
      ereturn(escontext, false,
          (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
           errmsg("malformed array literal: \"%s\"", origStr),
           errdetail("Missing \"%s\" after array dimensions.",
                 "]")));
    p++;

    /*
     * Note: we could accept ub = lb-1 to represent a zero-length
     * dimension.  However, that would result in an empty array, for which
     * we don't keep any dimension data, so that e.g. [1:0] and [101:100]
     * would be equivalent.  Given the lack of field demand, there seems
     * little point in allowing such cases.
     */
    if (ub < lBound[ndim])
      ereturn(escontext, false,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("upper bound cannot be less than lower bound")));

    /* Upper bound of INT_MAX must be disallowed, cf ArrayCheckBounds() */
    if (ub == INT_MAX)
      ereturn(escontext, false,
          (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
           errmsg("array upper bound is too large: %d", ub)));

    /* Compute "ub - lBound[ndim] + 1", detecting overflow */
    if (pg_sub_s32_overflow(ub, lBound[ndim], &ub) ||
      pg_add_s32_overflow(ub, 1, &ub))
      ereturn(escontext, false,
          (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
           errmsg("array size exceeds the maximum allowed (%zu)",
              MaxArraySize)));

    dim[ndim] = ub;
    ndim++;
  }

  *srcptr = p;
  *ndim_p = ndim;
  return true;
}

/*
 * ReadDimensionInt
 *   parse an integer, for the array dimensions
 *
 * On entry, *srcptr points to the string to parse. It is advanced past the
 * digits of the integer. If there are no digits, returns true and leaves
 * *srcptr unchanged.
 *
 * Result:
 *  true for success, false for failure (if escontext is provided).
 *  On success, the parsed integer is returned in *result.
 */
static bool
ReadDimensionInt(char **srcptr, int *result,
         const char *origStr, Node *escontext)
{
  char     *p = *srcptr;
  long    l;

  /* don't accept leading whitespace */
  if (!isdigit((unsigned char) *p) && *p != '-' && *p != '+')
  {
    *result = 0;
    return true;
  }

  errno = 0;
  l = strtol(p, srcptr, 10);

  if (errno == ERANGE || l > PG_INT32_MAX || l < PG_INT32_MIN)
    ereturn(escontext, false,
        (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
         errmsg("array bound is out of integer range")));

  *result = (int) l;
  return true;
}

/*
 * ReadArrayStr :
 *   parses the array string pointed to by *srcptr and converts the values
 *   to internal format.  Determines the array dimensions as it goes.
 *
 * On entry, *srcptr points to the string to parse (it must point to a '{').
 * On successful return, it is advanced to point past the closing '}'.
 *
 * If dimensions were specified explicitly, they are passed in *ndim_p and
 * dim[].  This function will check that the array values match the specified
 * dimensions.  If dimensions were not given, caller must pass *ndim_p == 0
 * and initialize all elements of dim[] to -1.  Then this function will
 * deduce the dimensions from the structure of the input and store them in
 * *ndim_p and the dim[] array.
 *
 * Element type information:
 *  inputproc: type-specific input procedure for element datatype.
 *  typioparam, typmod: auxiliary values to pass to inputproc.
 *  typdelim: the value delimiter (type-specific).
 *  typlen, typbyval, typalign: storage parameters of element datatype.
 *
 * Outputs:
 *  *ndim_p, dim: dimensions deduced from the input structure.
 *  *nitems_p: total number of elements.
 *  *values_p[]: palloc'd array, filled with converted data values.
 *  *nulls_p[]: palloc'd array, filled with is-null markers.
 *
 * 'origStr' is the original input string, used only in error messages.
 * If *escontext points to an ErrorSaveContext, details of any error are
 * reported there.
 *
 * Result:
 *  true for success, false for failure (if escontext is provided).
 */
static bool
ReadArrayStr(char **srcptr,
       FmgrInfo *inputproc,
       Oid typioparam,
       int32 typmod,
       char typdelim,
       int typlen,
       bool typbyval,
       char typalign,
       int *ndim_p,
       int *dim,
       int *nitems_p,
       Datum **values_p,
       bool **nulls_p,
       const char *origStr,
       Node *escontext)
{
  int     ndim = *ndim_p;
  bool    dimensions_specified = (ndim != 0);
  int     maxitems;
  Datum    *values;
  bool     *nulls;
  StringInfoData elembuf;
  int     nest_level;
  int     nitems;
  bool    ndim_frozen;
  bool    expect_delim;
  int     nelems[MAXDIM];

  /* Allocate some starting output workspace; we'll enlarge as needed */
  maxitems = 16;
  values = palloc_array(Datum, maxitems);
  nulls = palloc_array(bool, maxitems);

  /* Allocate workspace to hold (string representation of) one element */
  initStringInfo(&elembuf);

  /* Loop below assumes first token is ATOK_LEVEL_START */
  Assert(**srcptr == '{');

  /* Parse tokens until we reach the matching right brace */
  nest_level = 0;
  nitems = 0;
  ndim_frozen = dimensions_specified;
  expect_delim = false;
  do
  {
    ArrayToken  tok;

    tok = ReadArrayToken(srcptr, &elembuf, typdelim, origStr, escontext);

    switch (tok)
    {
      case ATOK_LEVEL_START:
        /* Can't write left brace where delim is expected */
        if (expect_delim)
          ereturn(escontext, false,
              (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
               errmsg("malformed array literal: \"%s\"", origStr),
               errdetail("Unexpected \"%c\" character.", '{')));

        /* Initialize element counting in the new level */
        if (nest_level >= MAXDIM)
          ereturn(escontext, false,
              (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
               errmsg("number of array dimensions exceeds the maximum allowed (%d)",
                  MAXDIM)));

        nelems[nest_level] = 0;
        nest_level++;
        if (nest_level > ndim)
        {
          /* Can't increase ndim once it's frozen */
          if (ndim_frozen)
            goto dimension_error;
          ndim = nest_level;
        }
        break;

      case ATOK_LEVEL_END:
        /* Can't get here with nest_level == 0 */
        Assert(nest_level > 0);

        /*
         * We allow a right brace to terminate an empty sub-array,
         * otherwise it must occur where we expect a delimiter.
         */
        if (nelems[nest_level - 1] > 0 && !expect_delim)
          ereturn(escontext, false,
              (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
               errmsg("malformed array literal: \"%s\"", origStr),
               errdetail("Unexpected \"%c\" character.",
                     '}')));
        nest_level--;
        /* Nested sub-arrays count as elements of outer level */
        if (nest_level > 0)
          nelems[nest_level - 1]++;

        /*
         * Note: if we had dimensionality info, then dim[nest_level]
         * is initially non-negative, and we'll check each sub-array's
         * length against that.
         */
        if (dim[nest_level] < 0)
        {
          /* Save length of first sub-array of this level */
          dim[nest_level] = nelems[nest_level];
        }
        else if (nelems[nest_level] != dim[nest_level])
        {
          /* Subsequent sub-arrays must have same length */
          goto dimension_error;
        }

        /*
         * Must have a delim or another right brace following, unless
         * we have reached nest_level 0, where this won't matter.
         */
        expect_delim = true;
        break;

      case ATOK_DELIM:
        if (!expect_delim)
          ereturn(escontext, false,
              (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
               errmsg("malformed array literal: \"%s\"", origStr),
               errdetail("Unexpected \"%c\" character.",
                     typdelim)));
        expect_delim = false;
        break;

      case ATOK_ELEM:
      case ATOK_ELEM_NULL:
        /* Can't get here with nest_level == 0 */
        Assert(nest_level > 0);

        /* Disallow consecutive ELEM tokens */
        if (expect_delim)
          ereturn(escontext, false,
              (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
               errmsg("malformed array literal: \"%s\"", origStr),
               errdetail("Unexpected array element.")));

        /* Enlarge the values/nulls arrays if needed */
        if (nitems >= maxitems)
        {
          if (maxitems >= MaxArraySize)
            ereturn(escontext, false,
                (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
                 errmsg("array size exceeds the maximum allowed (%zu)",
                    MaxArraySize)));
          maxitems = Min(maxitems * 2, MaxArraySize);
          values = repalloc_array(values, Datum, maxitems);
          nulls = repalloc_array(nulls, bool, maxitems);
        }

        /* Read the element's value, or check that NULL is allowed */
        if (!InputFunctionCallSafe(inputproc,
                       (tok == ATOK_ELEM_NULL) ? NULL : elembuf.data,
                       typioparam, typmod,
                       escontext,
                       &values[nitems]))
          return false;
        nulls[nitems] = (tok == ATOK_ELEM_NULL);
        nitems++;

        /*
         * Once we have found an element, the number of dimensions can
         * no longer increase, and subsequent elements must all be at
         * the same nesting depth.
         */
        ndim_frozen = true;
        if (nest_level != ndim)
          goto dimension_error;
        /* Count the new element */
        nelems[nest_level - 1]++;

        /* Must have a delim or a right brace following */
        expect_delim = true;
        break;

      case ATOK_ERROR:
        return false;
    }
  } while (nest_level > 0);

  /* Clean up and return results */
  pfree(elembuf.data);

  *ndim_p = ndim;
  *nitems_p = nitems;
  *values_p = values;
  *nulls_p = nulls;
  return true;

dimension_error:
  if (dimensions_specified)
    ereturn(escontext, false,
        (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
         errmsg("malformed array literal: \"%s\"", origStr),
         errdetail("Specified array dimensions do not match array contents.")));
  else
    ereturn(escontext, false,
        (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
         errmsg("malformed array literal: \"%s\"", origStr),
         errdetail("Multidimensional arrays must have sub-arrays with matching dimensions.")));
}

/*
 * ReadArrayToken
 *   read one token from an array value string
 *
 * Starts scanning from *srcptr.  On non-error return, *srcptr is
 * advanced past the token.
 *
 * If the token is ATOK_ELEM, the de-escaped string is returned in elembuf.
 */
static ArrayToken
ReadArrayToken(char **srcptr, StringInfo elembuf, char typdelim,
         const char *origStr, Node *escontext)
{
  char     *p = *srcptr;
  int     dstlen;
  bool    has_escapes;

  resetStringInfo(elembuf);

  /* Identify token type.  Loop advances over leading whitespace. */
  for (;;)
  {
    switch (*p)
    {
      case '\0':
        goto ending_error;
      case '{':
        *srcptr = p + 1;
        return ATOK_LEVEL_START;
      case '}':
        *srcptr = p + 1;
        return ATOK_LEVEL_END;
      case '"':
        p++;
        goto quoted_element;
      default:
        if (*p == typdelim)
        {
          *srcptr = p + 1;
          return ATOK_DELIM;
        }
        if (scanner_isspace(*p))
        {
          p++;
          continue;
        }
        goto unquoted_element;
    }
  }

quoted_element:
  for (;;)
  {
    switch (*p)
    {
      case '\0':
        goto ending_error;
      case '\\':
        /* Skip backslash, copy next character as-is. */
        p++;
        if (*p == '\0')
          goto ending_error;
        appendStringInfoChar(elembuf, *p++);
        break;
      case '"':

        /*
         * If next non-whitespace isn't typdelim or a brace, complain
         * about incorrect quoting.  While we could leave such cases
         * to be detected as incorrect token sequences, the resulting
         * message wouldn't be as helpful.  (We could also give the
         * incorrect-quoting error when next is '{', but treating that
         * as a token sequence error seems better.)
         */
        while (*(++p) != '\0')
        {
          if (*p == typdelim || *p == '}' || *p == '{')
          {
            *srcptr = p;
            return ATOK_ELEM;
          }
          if (!scanner_isspace(*p))
            ereturn(escontext, ATOK_ERROR,
                (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
                 errmsg("malformed array literal: \"%s\"", origStr),
                 errdetail("Incorrectly quoted array element.")));
        }
        goto ending_error;
      default:
        appendStringInfoChar(elembuf, *p++);
        break;
    }
  }

unquoted_element:

  /*
   * We don't include trailing whitespace in the result.  dstlen tracks how
   * much of the output string is known to not be trailing whitespace.
   */
  dstlen = 0;
  has_escapes = false;
  for (;;)
  {
    switch (*p)
    {
      case '\0':
        goto ending_error;
      case '{':
        ereturn(escontext, ATOK_ERROR,
            (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
             errmsg("malformed array literal: \"%s\"", origStr),
             errdetail("Unexpected \"%c\" character.",
                   '{')));
      case '"':
        /* Must double-quote all or none of an element. */
        ereturn(escontext, ATOK_ERROR,
            (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
             errmsg("malformed array literal: \"%s\"", origStr),
             errdetail("Incorrectly quoted array element.")));
      case '\\':
        /* Skip backslash, copy next character as-is. */
        p++;
        if (*p == '\0')
          goto ending_error;
        appendStringInfoChar(elembuf, *p++);
        dstlen = elembuf->len;  /* treat it as non-whitespace */
        has_escapes = true;
        break;
      default:
        /* End of elem? */
        if (*p == typdelim || *p == '}')
        {
          /* hack: truncate the output string to dstlen */
          elembuf->data[dstlen] = '\0';
          elembuf->len = dstlen;
          *srcptr = p;
          /* Check if it's unquoted "NULL" */
          if (Array_nulls && !has_escapes &&
            pg_strcasecmp(elembuf->data, "NULL") == 0)
            return ATOK_ELEM_NULL;
          else
            return ATOK_ELEM;
        }
        appendStringInfoChar(elembuf, *p);
        if (!scanner_isspace(*p))
          dstlen = elembuf->len;
        p++;
        break;
    }
  }

ending_error:
  ereturn(escontext, ATOK_ERROR,
      (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
       errmsg("malformed array literal: \"%s\"", origStr),
       errdetail("Unexpected end of input.")));
}

/*
 * Copy data into an array object from a temporary array of Datums.
 *
 * array: array object (with header fields already filled in)
 * values: array of Datums to be copied
 * nulls: array of is-null flags (can be NULL if no nulls)
 * nitems: number of Datums to be copied
 * typbyval, typlen, typalign: info about element datatype
 * freedata: if true and element type is pass-by-ref, pfree data values
 * referenced by Datums after copying them.
 *
 * If the input data is of varlena type, the caller must have ensured that
 * the values are not toasted.  (Doing it here doesn't work since the
 * caller has already allocated space for the array...)
 */
void
CopyArrayEls(ArrayType *array,
       const Datum *values,
       const bool *nulls,
       int nitems,
       int typlen,
       bool typbyval,
       char typalign,
       bool freedata)
{
  char     *p = ARR_DATA_PTR(array);
  uint8    *bitmap = ARR_NULLBITMAP(array);
  int     bitval = 0;
  int     bitmask = 1;
  uint8   typalignby = typalign_to_alignby(typalign);
  int     i;

  if (typbyval)
    freedata = false;

  for (i = 0; i < nitems; i++)
  {
    if (nulls && nulls[i])
    {
      if (!bitmap)   /* shouldn't happen */
        elog(ERROR, "null array element where not supported");
      /* bitmap bit stays 0 */
    }
    else
    {
      bitval |= bitmask;
      p += ArrayCastAndSet(values[i], typlen, typbyval, typalignby, p);
      if (freedata)
        pfree(DatumGetPointer(values[i]));
    }
    if (bitmap)
    {
      bitmask <<= 1;
      if (bitmask == 0x100)
      {
        *bitmap++ = bitval;
        bitval = 0;
        bitmask = 1;
      }
    }
  }

  if (bitmap && bitmask != 1)
    *bitmap = bitval;
}

/*
 * array_out :
 *       takes the internal representation of an array and returns a string
 *      containing the array in its external format.
 */
Datum
array_out(PG_FUNCTION_ARGS)
{
  AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);
  Oid     element_type = AARR_ELEMTYPE(v);
  int     typlen;
  bool    typbyval;
  char    typalign;
  char    typdelim;
  char     *p,
         *tmp,
         *retval,
        **values,
        dims_str[(MAXDIM * 33) + 2];

  /*
   * 33 per dim since we assume 15 digits per number + ':' +'[]'
   *
   * +2 allows for assignment operator + trailing null
   */
  bool     *needquotes,
        needdims = false;
  size_t    overall_length;
  int     nitems,
        i,
        j,
        k,
        indx[MAXDIM];
  int     ndim,
         *dims,
         *lb;
  array_iter  iter;
  ArrayMetaState *my_extra;

  /*
   * We arrange to look up info about element type, including its output
   * conversion proc, 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 info about element type, including its output conversion proc
     */
    get_type_io_data(element_type, IOFunc_output,
             &my_extra->typlen, &my_extra->typbyval,
             &my_extra->typalign, &my_extra->typdelim,
             &my_extra->typioparam, &my_extra->typiofunc);
    fmgr_info_cxt(my_extra->typiofunc, &my_extra->proc,
            fcinfo->flinfo->fn_mcxt);
    my_extra->element_type = element_type;
  }
  typlen = my_extra->typlen;
  typbyval = my_extra->typbyval;
  typalign = my_extra->typalign;
  typdelim = my_extra->typdelim;

  ndim = AARR_NDIM(v);
  dims = AARR_DIMS(v);
  lb = AARR_LBOUND(v);
  nitems = ArrayGetNItems(ndim, dims);

  if (nitems == 0)
  {
    retval = pstrdup("{}");
    PG_RETURN_CSTRING(retval);
  }

  /*
   * we will need to add explicit dimensions if any dimension has a lower
   * bound other than one
   */
  for (i = 0; i < ndim; i++)
  {
    if (lb[i] != 1)
    {
      needdims = true;
      break;
    }
  }

  /*
   * Convert all values to string form, count total space needed (including
   * any overhead such as escaping backslashes), and detect whether each
   * item needs double quotes.
   */
  values = (char **) palloc(nitems * sizeof(char *));
  needquotes = (bool *) palloc(nitems * sizeof(bool));
  overall_length = 0;

  array_iter_setup(&iter, v, typlen, typbyval, typalign);

  for (i = 0; i < nitems; i++)
  {
    Datum   itemvalue;
    bool    isnull;
    bool    needquote;

    /* Get source element, checking for NULL */
    itemvalue = array_iter_next(&iter, &isnull, i);

    if (isnull)
    {
      values[i] = pstrdup("NULL");
      overall_length += 4;
      needquote = false;
    }
    else
    {
      values[i] = OutputFunctionCall(&my_extra->proc, itemvalue);

      /* count data plus backslashes; detect chars needing quotes */
      if (values[i][0] == '\0')
        needquote = true; /* force quotes for empty string */
      else if (pg_strcasecmp(values[i], "NULL") == 0)
        needquote = true; /* force quotes for literal NULL */
      else
        needquote = false;

      for (tmp = values[i]; *tmp != '\0'; tmp++)
      {
        char    ch = *tmp;

        overall_length += 1;
        if (ch == '"' || ch == '\\')
        {
          needquote = true;
          overall_length += 1;
        }
        else if (ch == '{' || ch == '}' || ch == typdelim ||
             scanner_isspace(ch))
          needquote = true;
      }
    }

    needquotes[i] = needquote;

    /* Count the pair of double quotes, if needed */
    if (needquote)
      overall_length += 2;
    /* and the comma (or other typdelim delimiter) */
    overall_length += 1;
  }

  /*
   * The very last array element doesn't have a typdelim delimiter after it,
   * but that's OK; that space is needed for the trailing '\0'.
   *
   * Now count total number of curly brace pairs in output string.
   */
  for (i = j = 0, k = 1; i < ndim; i++)
  {
    j += k, k *= dims[i];
  }
  overall_length += 2 * j;

  /* Format explicit dimensions if required */
  dims_str[0] = '\0';
  if (needdims)
  {
    char     *ptr = dims_str;

    for (i = 0; i < ndim; i++)
    {
      sprintf(ptr, "[%d:%d]", lb[i], lb[i] + dims[i] - 1);
      ptr += strlen(ptr);
    }
    *ptr++ = *ASSGN;
    *ptr = '\0';
    overall_length += ptr - dims_str;
  }

  /* Now construct the output string */
  retval = (char *) palloc(overall_length);
  p = retval;

#define APPENDSTR(str)  (strcpy(p, (str)), p += strlen(p))
#define APPENDCHAR(ch)  (*p++ = (ch), *p = '\0')

  if (needdims)
    APPENDSTR(dims_str);
  APPENDCHAR('{');
  for (i = 0; i < ndim; i++)
    indx[i] = 0;
  j = 0;
  k = 0;
  do
  {
    for (i = j; i < ndim - 1; i++)
      APPENDCHAR('{');

    if (needquotes[k])
    {
      APPENDCHAR('"');
      for (tmp = values[k]; *tmp; tmp++)
      {
        char    ch = *tmp;

        if (ch == '"' || ch == '\\')
          *p++ = '\\';
        *p++ = ch;
      }
      *p = '\0';
      APPENDCHAR('"');
    }
    else
      APPENDSTR(values[k]);
    pfree(values[k++]);

    for (i = ndim - 1; i >= 0; i--)
    {
      if (++(indx[i]) < dims[i])
      {
        APPENDCHAR(typdelim);
        break;
      }
      else
      {
        indx[i] = 0;
        APPENDCHAR('}');
      }
    }
    j = i;
  } while (j != -1);

#undef APPENDSTR
#undef APPENDCHAR

  /* Assert that we calculated the string length accurately */
  Assert(overall_length == (p - retval + 1));

  pfree(values);
  pfree(needquotes);

  PG_RETURN_CSTRING(retval);
}

/*
 * array_recv :
 *      converts an array from the external binary format to
 *      its internal format.
 *
 * return value :
 *      the internal representation of the input array
 */
Datum
array_recv(PG_FUNCTION_ARGS)
{
  StringInfo  buf = (StringInfo) PG_GETARG_POINTER(0);
  Oid     spec_element_type = PG_GETARG_OID(1);  /* type of an array
                             * element */
  int32   typmod = PG_GETARG_INT32(2);  /* typmod for array elements */
  Oid     element_type;
  int     typlen;
  bool    typbyval;
  char    typalign;
  Oid     typioparam;
  int     i,
        nitems;
  Datum    *dataPtr;
  bool     *nullsPtr;
  bool    hasnulls;
  int32   nbytes;
  int32   dataoffset;
  ArrayType  *retval;
  int     ndim,
        flags,
        dim[MAXDIM],
        lBound[MAXDIM];
  ArrayMetaState *my_extra;

  /* Get the array header information */
  ndim = pq_getmsgint(buf, 4);
  if (ndim < 0)       /* we do allow zero-dimension arrays */
    ereport(ERROR,
        (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
         errmsg("invalid number of dimensions: %d", ndim)));
  if (ndim > MAXDIM)
    ereport(ERROR,
        (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
         errmsg("number of array dimensions (%d) exceeds the maximum allowed (%d)",
            ndim, MAXDIM)));

  flags = pq_getmsgint(buf, 4);
  if (flags != 0 && flags != 1)
    ereport(ERROR,
        (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
         errmsg("invalid array flags")));

  /* Check element type recorded in the data */
  element_type = pq_getmsgint(buf, sizeof(Oid));

  /*
   * From a security standpoint, it doesn't matter whether the input's
   * element type matches what we expect: the element type's receive
   * function has to be robust enough to cope with invalid data.  However,
   * from a user-friendliness standpoint, it's nicer to complain about type
   * mismatches than to throw "improper binary format" errors.  But there's
   * a problem: only built-in types have OIDs that are stable enough to
   * believe that a mismatch is a real issue.  So complain only if both OIDs
   * are in the built-in range.  Otherwise, carry on with the element type
   * we "should" be getting.
   */
  if (element_type != spec_element_type)
  {
    if (element_type < FirstGenbkiObjectId &&
      spec_element_type < FirstGenbkiObjectId)
      ereport(ERROR,
          (errcode(ERRCODE_DATATYPE_MISMATCH),
           errmsg("binary data has array element type %u (%s) instead of expected %u (%s)",
              element_type,
              format_type_extended(element_type, -1,
                         FORMAT_TYPE_ALLOW_INVALID),
              spec_element_type,
              format_type_extended(spec_element_type, -1,
                         FORMAT_TYPE_ALLOW_INVALID))));
    element_type = spec_element_type;
  }

  for (i = 0; i < ndim; i++)
  {
    dim[i] = pq_getmsgint(buf, 4);
    lBound[i] = pq_getmsgint(buf, 4);
  }

  /* This checks for overflow of array dimensions */
  nitems = ArrayGetNItems(ndim, dim);
  ArrayCheckBounds(ndim, dim, lBound);

  /*
   * We arrange to look up info about element type, including its receive
   * conversion proc, 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 info about element type, including its receive proc */
    get_type_io_data(element_type, IOFunc_receive,
             &my_extra->typlen, &my_extra->typbyval,
             &my_extra->typalign, &my_extra->typdelim,
             &my_extra->typioparam, &my_extra->typiofunc);
    if (!OidIsValid(my_extra->typiofunc))
      ereport(ERROR,
          (errcode(ERRCODE_UNDEFINED_FUNCTION),
           errmsg("no binary input function available for type %s",
              format_type_be(element_type))));
    fmgr_info_cxt(my_extra->typiofunc, &my_extra->proc,
            fcinfo->flinfo->fn_mcxt);
    my_extra->element_type = element_type;
  }

  if (nitems == 0)
  {
    /* Return empty array ... but not till we've validated element_type */
    PG_RETURN_ARRAYTYPE_P(construct_empty_array(element_type));
  }

  typlen = my_extra->typlen;
  typbyval = my_extra->typbyval;
  typalign = my_extra->typalign;
  typioparam = my_extra->typioparam;

  dataPtr = (Datum *) palloc(nitems * sizeof(Datum));
  nullsPtr = (bool *) palloc(nitems * sizeof(bool));
  ReadArrayBinary(buf, nitems,
          &my_extra->proc, typioparam, typmod,
          typlen, typbyval, typalign,
          dataPtr, nullsPtr,
          &hasnulls, &nbytes);
  if (hasnulls)
  {
    dataoffset = ARR_OVERHEAD_WITHNULLS(ndim, nitems);
    nbytes += dataoffset;
  }
  else
  {
    dataoffset = 0;     /* marker for no null bitmap */
    nbytes += ARR_OVERHEAD_NONULLS(ndim);
  }
  retval = (ArrayType *) palloc0(nbytes);
  SET_VARSIZE(retval, nbytes);
  retval->ndim = ndim;
  retval->dataoffset = dataoffset;
  retval->elemtype = element_type;
  memcpy(ARR_DIMS(retval), dim, ndim * sizeof(int));
  memcpy(ARR_LBOUND(retval), lBound, ndim * sizeof(int));

  CopyArrayEls(retval,
         dataPtr, nullsPtr, nitems,
         typlen, typbyval, typalign,
         true);

  pfree(dataPtr);
  pfree(nullsPtr);

  PG_RETURN_ARRAYTYPE_P(retval);
}

/*
 * ReadArrayBinary:
 *   collect the data elements of an array being read in binary style.
 *
 * Inputs:
 *  buf: the data buffer to read from.
 *  nitems: total number of array elements (already read).
 *  receiveproc: type-specific receive procedure for element datatype.
 *  typioparam, typmod: auxiliary values to pass to receiveproc.
 *  typlen, typbyval, typalign: storage parameters of element datatype.
 *
 * Outputs:
 *  values[]: filled with converted data values.
 *  nulls[]: filled with is-null markers.
 *  *hasnulls: set true iff there are any null elements.
 *  *nbytes: set to total size of data area needed (including alignment
 *    padding but not including array header overhead).
 *
 * Note that values[] and nulls[] are allocated by the caller, and must have
 * nitems elements.
 */
static void
ReadArrayBinary(StringInfo buf,
        int nitems,
        FmgrInfo *receiveproc,
        Oid typioparam,
        int32 typmod,
        int typlen,
        bool typbyval,
        char typalign,
        Datum *values,
        bool *nulls,
        bool *hasnulls,
        int32 *nbytes)
{
  int     i;
  bool    hasnull;
  int32   totbytes;
  uint8   typalignby = typalign_to_alignby(typalign);

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

    /* Get and check the item length */
    itemlen = pq_getmsgint(buf, 4);
    if (itemlen < -1 || itemlen > (buf->len - buf->cursor))
      ereport(ERROR,
          (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
           errmsg("insufficient data left in message")));

    if (itemlen == -1)
    {
      /* -1 length means NULL */
      values[i] = ReceiveFunctionCall(receiveproc, NULL,
                      typioparam, typmod);
      nulls[i] = true;
      continue;
    }

    /*
     * 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 */
    values[i] = ReceiveFunctionCall(receiveproc, &elem_buf,
                    typioparam, typmod);
    nulls[i] = false;

    /* Trouble if it didn't eat the whole buffer */
    if (elem_buf.cursor != itemlen)
      ereport(ERROR,
          (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
           errmsg("improper binary format in array element %d",
              i + 1)));
  }

  /*
   * Check for nulls, compute total data space needed
   */
  hasnull = false;
  totbytes = 0;
  for (i = 0; i < nitems; i++)
  {
    if (nulls[i])
      hasnull = true;
    else
    {
      /* let's just make sure data is not toasted */
      if (typlen == -1)
        values[i] = PointerGetDatum(PG_DETOAST_DATUM(values[i]));
      totbytes = att_addlength_datum(totbytes, typlen, values[i]);
      totbytes = att_nominal_alignby(totbytes, typalignby);
      /* check for overflow of total request */
      if (!AllocSizeIsValid(totbytes))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxAllocSize)));
    }
  }
  *hasnulls = hasnull;
  *nbytes = totbytes;
}


/*
 * array_send :
 *      takes the internal representation of an array and returns a bytea
 *      containing the array in its external binary format.
 */
Datum
array_send(PG_FUNCTION_ARGS)
{
  AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);
  Oid     element_type = AARR_ELEMTYPE(v);
  int     typlen;
  bool    typbyval;
  char    typalign;
  int     nitems,
        i;
  int     ndim,
         *dim,
         *lb;
  StringInfoData buf;
  array_iter  iter;
  ArrayMetaState *my_extra;

  /*
   * We arrange to look up info about element type, including its send
   * conversion proc, 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 info about element type, including its send proc */
    get_type_io_data(element_type, IOFunc_send,
             &my_extra->typlen, &my_extra->typbyval,
             &my_extra->typalign, &my_extra->typdelim,
             &my_extra->typioparam, &my_extra->typiofunc);
    if (!OidIsValid(my_extra->typiofunc))
      ereport(ERROR,
          (errcode(ERRCODE_UNDEFINED_FUNCTION),
           errmsg("no binary output function available for type %s",
              format_type_be(element_type))));
    fmgr_info_cxt(my_extra->typiofunc, &my_extra->proc,
            fcinfo->flinfo->fn_mcxt);
    my_extra->element_type = element_type;
  }
  typlen = my_extra->typlen;
  typbyval = my_extra->typbyval;
  typalign = my_extra->typalign;

  ndim = AARR_NDIM(v);
  dim = AARR_DIMS(v);
  lb = AARR_LBOUND(v);
  nitems = ArrayGetNItems(ndim, dim);

  pq_begintypsend(&buf);

  /* Send the array header information */
  pq_sendint32(&buf, ndim);
  pq_sendint32(&buf, AARR_HASNULL(v) ? 1 : 0);
  pq_sendint32(&buf, element_type);
  for (i = 0; i < ndim; i++)
  {
    pq_sendint32(&buf, dim[i]);
    pq_sendint32(&buf, lb[i]);
  }

  /* Send the array elements using the element's own sendproc */
  array_iter_setup(&iter, v, typlen, typbyval, typalign);

  for (i = 0; i < nitems; i++)
  {
    Datum   itemvalue;
    bool    isnull;

    /* Get source element, checking for NULL */
    itemvalue = array_iter_next(&iter, &isnull, i);

    if (isnull)
    {
      /* -1 length means a NULL */
      pq_sendint32(&buf, -1);
    }
    else
    {
      bytea    *outputbytes;

      outputbytes = SendFunctionCall(&my_extra->proc, itemvalue);
      pq_sendint32(&buf, VARSIZE(outputbytes) - VARHDRSZ);
      pq_sendbytes(&buf, VARDATA(outputbytes),
             VARSIZE(outputbytes) - VARHDRSZ);
      pfree(outputbytes);
    }
  }

  PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
}

/*
 * array_ndims :
 *      returns the number of dimensions of the array pointed to by "v"
 */
Datum
array_ndims(PG_FUNCTION_ARGS)
{
  AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);

  /* Sanity check: does it look like an array at all? */
  if (AARR_NDIM(v) <= 0 || AARR_NDIM(v) > MAXDIM)
    PG_RETURN_NULL();

  PG_RETURN_INT32(AARR_NDIM(v));
}

/*
 * array_dims :
 *      returns the dimensions of the array pointed to by "v", as a "text"
 */
Datum
array_dims(PG_FUNCTION_ARGS)
{
  AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);
  char     *p;
  int     i;
  int      *dimv,
         *lb;

  /*
   * 33 since we assume 15 digits per number + ':' +'[]'
   *
   * +1 for trailing null
   */
  char    buf[MAXDIM * 33 + 1];

  /* Sanity check: does it look like an array at all? */
  if (AARR_NDIM(v) <= 0 || AARR_NDIM(v) > MAXDIM)
    PG_RETURN_NULL();

  dimv = AARR_DIMS(v);
  lb = AARR_LBOUND(v);

  p = buf;
  for (i = 0; i < AARR_NDIM(v); i++)
  {
    sprintf(p, "[%d:%d]", lb[i], dimv[i] + lb[i] - 1);
    p += strlen(p);
  }

  PG_RETURN_TEXT_P(cstring_to_text(buf));
}

/*
 * array_lower :
 *    returns the lower dimension, of the DIM requested, for
 *    the array pointed to by "v", as an int4
 */
Datum
array_lower(PG_FUNCTION_ARGS)
{
  AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);
  int     reqdim = PG_GETARG_INT32(1);
  int      *lb;
  int     result;

  /* Sanity check: does it look like an array at all? */
  if (AARR_NDIM(v) <= 0 || AARR_NDIM(v) > MAXDIM)
    PG_RETURN_NULL();

  /* Sanity check: was the requested dim valid */
  if (reqdim <= 0 || reqdim > AARR_NDIM(v))
    PG_RETURN_NULL();

  lb = AARR_LBOUND(v);
  result = lb[reqdim - 1];

  PG_RETURN_INT32(result);
}

/*
 * array_upper :
 *    returns the upper dimension, of the DIM requested, for
 *    the array pointed to by "v", as an int4
 */
Datum
array_upper(PG_FUNCTION_ARGS)
{
  AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);
  int     reqdim = PG_GETARG_INT32(1);
  int      *dimv,
         *lb;
  int     result;

  /* Sanity check: does it look like an array at all? */
  if (AARR_NDIM(v) <= 0 || AARR_NDIM(v) > MAXDIM)
    PG_RETURN_NULL();

  /* Sanity check: was the requested dim valid */
  if (reqdim <= 0 || reqdim > AARR_NDIM(v))
    PG_RETURN_NULL();

  lb = AARR_LBOUND(v);
  dimv = AARR_DIMS(v);

  result = dimv[reqdim - 1] + lb[reqdim - 1] - 1;

  PG_RETURN_INT32(result);
}

/*
 * array_length :
 *    returns the length, of the dimension requested, for
 *    the array pointed to by "v", as an int4
 */
Datum
array_length(PG_FUNCTION_ARGS)
{
  AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);
  int     reqdim = PG_GETARG_INT32(1);
  int      *dimv;
  int     result;

  /* Sanity check: does it look like an array at all? */
  if (AARR_NDIM(v) <= 0 || AARR_NDIM(v) > MAXDIM)
    PG_RETURN_NULL();

  /* Sanity check: was the requested dim valid */
  if (reqdim <= 0 || reqdim > AARR_NDIM(v))
    PG_RETURN_NULL();

  dimv = AARR_DIMS(v);

  result = dimv[reqdim - 1];

  PG_RETURN_INT32(result);
}

/*
 * array_cardinality:
 *    returns the total number of elements in an array
 */
Datum
array_cardinality(PG_FUNCTION_ARGS)
{
  AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);

  PG_RETURN_INT32(ArrayGetNItems(AARR_NDIM(v), AARR_DIMS(v)));
}


/*
 * array_get_element :
 *    This routine takes an array datum and a subscript array and returns
 *    the referenced item as a Datum.  Note that for a pass-by-reference
 *    datatype, the returned Datum is a pointer into the array object.
 *
 * This handles both ordinary varlena arrays and fixed-length arrays.
 *
 * Inputs:
 *  arraydatum: the array object (mustn't be NULL)
 *  nSubscripts: number of subscripts supplied
 *  indx[]: the subscript values
 *  arraytyplen: pg_type.typlen for the array type
 *  elmlen: pg_type.typlen for the array's element type
 *  elmbyval: pg_type.typbyval for the array's element type
 *  elmalign: pg_type.typalign for the array's element type
 *
 * Outputs:
 *  The return value is the element Datum.
 *  *isNull is set to indicate whether the element is NULL.
 */
Datum
array_get_element(Datum arraydatum,
          int nSubscripts,
          int *indx,
          int arraytyplen,
          int elmlen,
          bool elmbyval,
          char elmalign,
          bool *isNull)
{
  int     i,
        ndim,
         *dim,
         *lb,
        offset,
        fixedDim[1],
        fixedLb[1];
  char     *arraydataptr,
         *retptr;
  uint8    *arraynullsptr;

  if (arraytyplen > 0)
  {
    /*
     * fixed-length arrays -- these are assumed to be 1-d, 0-based
     */
    ndim = 1;
    fixedDim[0] = arraytyplen / elmlen;
    fixedLb[0] = 0;
    dim = fixedDim;
    lb = fixedLb;
    arraydataptr = (char *) DatumGetPointer(arraydatum);
    arraynullsptr = NULL;
  }
  else if (VARATT_IS_EXTERNAL_EXPANDED(DatumGetPointer(arraydatum)))
  {
    /* expanded array: let's do this in a separate function */
    return array_get_element_expanded(arraydatum,
                      nSubscripts,
                      indx,
                      arraytyplen,
                      elmlen,
                      elmbyval,
                      elmalign,
                      isNull);
  }
  else
  {
    /* detoast array if necessary, producing normal varlena input */
    ArrayType  *array = DatumGetArrayTypeP(arraydatum);

    ndim = ARR_NDIM(array);
    dim = ARR_DIMS(array);
    lb = ARR_LBOUND(array);
    arraydataptr = ARR_DATA_PTR(array);
    arraynullsptr = ARR_NULLBITMAP(array);
  }

  /*
   * Return NULL for invalid subscript
   */
  if (ndim != nSubscripts || ndim <= 0 || ndim > MAXDIM)
  {
    *isNull = true;
    return (Datum) 0;
  }
  for (i = 0; i < ndim; i++)
  {
    if (indx[i] < lb[i] || indx[i] >= (dim[i] + lb[i]))
    {
      *isNull = true;
      return (Datum) 0;
    }
  }

  /*
   * Calculate the element number
   */
  offset = ArrayGetOffset(nSubscripts, dim, lb, indx);

  /*
   * Check for NULL array element
   */
  if (array_get_isnull(arraynullsptr, offset))
  {
    *isNull = true;
    return (Datum) 0;
  }

  /*
   * OK, get the element
   */
  *isNull = false;
  retptr = array_seek(arraydataptr, 0, arraynullsptr, offset,
            elmlen, elmbyval, elmalign);
  return ArrayCast(retptr, elmbyval, elmlen);
}

/*
 * Implementation of array_get_element() for an expanded array
 */
static Datum
array_get_element_expanded(Datum arraydatum,
               int nSubscripts, int *indx,
               int arraytyplen,
               int elmlen, bool elmbyval, char elmalign,
               bool *isNull)
{
  ExpandedArrayHeader *eah;
  int     i,
        ndim,
         *dim,
         *lb,
        offset;
  Datum    *dvalues;
  bool     *dnulls;

  eah = (ExpandedArrayHeader *) DatumGetEOHP(arraydatum);
  Assert(eah->ea_magic == EA_MAGIC);

  /* sanity-check caller's info against object */
  Assert(arraytyplen == -1);
  Assert(elmlen == eah->typlen);
  Assert(elmbyval == eah->typbyval);
  Assert(elmalign == eah->typalign);

  ndim = eah->ndims;
  dim = eah->dims;
  lb = eah->lbound;

  /*
   * Return NULL for invalid subscript
   */
  if (ndim != nSubscripts || ndim <= 0 || ndim > MAXDIM)
  {
    *isNull = true;
    return (Datum) 0;
  }
  for (i = 0; i < ndim; i++)
  {
    if (indx[i] < lb[i] || indx[i] >= (dim[i] + lb[i]))
    {
      *isNull = true;
      return (Datum) 0;
    }
  }

  /*
   * Calculate the element number
   */
  offset = ArrayGetOffset(nSubscripts, dim, lb, indx);

  /*
   * Deconstruct array if we didn't already.  Note that we apply this even
   * if the input is nominally read-only: it should be safe enough.
   */
  deconstruct_expanded_array(eah);

  dvalues = eah->dvalues;
  dnulls = eah->dnulls;

  /*
   * Check for NULL array element
   */
  if (dnulls && dnulls[offset])
  {
    *isNull = true;
    return (Datum) 0;
  }

  /*
   * OK, get the element.  It's OK to return a pass-by-ref value as a
   * pointer into the expanded array, for the same reason that regular
   * array_get_element can return a pointer into flat arrays: the value is
   * assumed not to change for as long as the Datum reference can exist.
   */
  *isNull = false;
  return dvalues[offset];
}

/*
 * array_get_slice :
 *       This routine takes an array and a range of indices (upperIndx and
 *       lowerIndx), creates a new array structure for the referred elements
 *       and returns a pointer to it.
 *
 * This handles both ordinary varlena arrays and fixed-length arrays.
 *
 * Inputs:
 *  arraydatum: the array object (mustn't be NULL)
 *  nSubscripts: number of subscripts supplied (must be same for upper/lower)
 *  upperIndx[]: the upper subscript values
 *  lowerIndx[]: the lower subscript values
 *  upperProvided[]: true for provided upper subscript values
 *  lowerProvided[]: true for provided lower subscript values
 *  arraytyplen: pg_type.typlen for the array type
 *  elmlen: pg_type.typlen for the array's element type
 *  elmbyval: pg_type.typbyval for the array's element type
 *  elmalign: pg_type.typalign for the array's element type
 *
 * Outputs:
 *  The return value is the new array Datum (it's never NULL)
 *
 * Omitted upper and lower subscript values are replaced by the corresponding
 * array bound.
 *
 * NOTE: we assume it is OK to scribble on the provided subscript arrays
 * lowerIndx[] and upperIndx[]; also, these arrays must be of size MAXDIM
 * even when nSubscripts is less.  These are generally just temporaries.
 */
Datum
array_get_slice(Datum arraydatum,
        int nSubscripts,
        int *upperIndx,
        int *lowerIndx,
        bool *upperProvided,
        bool *lowerProvided,
        int arraytyplen,
        int elmlen,
        bool elmbyval,
        char elmalign)
{
  ArrayType  *array;
  ArrayType  *newarray;
  int     i,
        ndim,
         *dim,
         *lb,
         *newlb;
  int     fixedDim[1],
        fixedLb[1];
  Oid     elemtype;
  char     *arraydataptr;
  uint8    *arraynullsptr;
  int32   dataoffset;
  int     bytes,
        span[MAXDIM];

  if (arraytyplen > 0)
  {
    /*
     * fixed-length arrays -- currently, cannot slice these because parser
     * labels output as being of the fixed-length array type! Code below
     * shows how we could support it if the parser were changed to label
     * output as a suitable varlena array type.
     */
    ereport(ERROR,
        (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
         errmsg("slices of fixed-length arrays not implemented")));

    /*
     * fixed-length arrays -- these are assumed to be 1-d, 0-based
     *
     * XXX where would we get the correct ELEMTYPE from?
     */
    ndim = 1;
    fixedDim[0] = arraytyplen / elmlen;
    fixedLb[0] = 0;
    dim = fixedDim;
    lb = fixedLb;
    elemtype = InvalidOid; /* XXX */
    arraydataptr = (char *) DatumGetPointer(arraydatum);
    arraynullsptr = NULL;
  }
  else
  {
    /* detoast input array if necessary */
    array = DatumGetArrayTypeP(arraydatum);

    ndim = ARR_NDIM(array);
    dim = ARR_DIMS(array);
    lb = ARR_LBOUND(array);
    elemtype = ARR_ELEMTYPE(array);
    arraydataptr = ARR_DATA_PTR(array);
    arraynullsptr = ARR_NULLBITMAP(array);
  }

  /*
   * Check provided subscripts.  A slice exceeding the current array limits
   * is silently truncated to the array limits.  If we end up with an empty
   * slice, return an empty array.
   */
  if (ndim < nSubscripts || ndim <= 0 || ndim > MAXDIM)
    return PointerGetDatum(construct_empty_array(elemtype));

  for (i = 0; i < nSubscripts; i++)
  {
    if (!lowerProvided[i] || lowerIndx[i] < lb[i])
      lowerIndx[i] = lb[i];
    if (!upperProvided[i] || upperIndx[i] >= (dim[i] + lb[i]))
      upperIndx[i] = dim[i] + lb[i] - 1;
    if (lowerIndx[i] > upperIndx[i])
      return PointerGetDatum(construct_empty_array(elemtype));
  }
  /* fill any missing subscript positions with full array range */
  for (; i < ndim; i++)
  {
    lowerIndx[i] = lb[i];
    upperIndx[i] = dim[i] + lb[i] - 1;
    if (lowerIndx[i] > upperIndx[i])
      return PointerGetDatum(construct_empty_array(elemtype));
  }

  mda_get_range(ndim, span, lowerIndx, upperIndx);

  bytes = array_slice_size(arraydataptr, arraynullsptr,
               ndim, dim, lb,
               lowerIndx, upperIndx,
               elmlen, elmbyval, elmalign);

  /*
   * Currently, we put a null bitmap in the result if the source has one;
   * could be smarter ...
   */
  if (arraynullsptr)
  {
    dataoffset = ARR_OVERHEAD_WITHNULLS(ndim, ArrayGetNItems(ndim, span));
    bytes += dataoffset;
  }
  else
  {
    dataoffset = 0;     /* marker for no null bitmap */
    bytes += ARR_OVERHEAD_NONULLS(ndim);
  }

  newarray = (ArrayType *) palloc0(bytes);
  SET_VARSIZE(newarray, bytes);
  newarray->ndim = ndim;
  newarray->dataoffset = dataoffset;
  newarray->elemtype = elemtype;
  memcpy(ARR_DIMS(newarray), span, ndim * sizeof(int));

  /*
   * Lower bounds of the new array are set to 1.  Formerly (before 7.3) we
   * copied the given lowerIndx values ... but that seems confusing.
   */
  newlb = ARR_LBOUND(newarray);
  for (i = 0; i < ndim; i++)
    newlb[i] = 1;

  array_extract_slice(newarray,
            ndim, dim, lb,
            arraydataptr, arraynullsptr,
            lowerIndx, upperIndx,
            elmlen, elmbyval, elmalign);

  return PointerGetDatum(newarray);
}

/*
 * array_set_element :
 *      This routine sets the value of one array element (specified by
 *      a subscript array) to a new value specified by "dataValue".
 *
 * This handles both ordinary varlena arrays and fixed-length arrays.
 *
 * Inputs:
 *  arraydatum: the initial array object (mustn't be NULL)
 *  nSubscripts: number of subscripts supplied
 *  indx[]: the subscript values
 *  dataValue: the datum to be inserted at the given position
 *  isNull: whether dataValue is NULL
 *  arraytyplen: pg_type.typlen for the array type
 *  elmlen: pg_type.typlen for the array's element type
 *  elmbyval: pg_type.typbyval for the array's element type
 *  elmalign: pg_type.typalign for the array's element type
 *
 * Result:
 *      A new array is returned, just like the old except for the one
 *      modified entry.  The original array object is not changed,
 *      unless what is passed is a read-write reference to an expanded
 *      array object; in that case the expanded array is updated in-place.
 *
 * For one-dimensional arrays only, we allow the array to be extended
 * by assigning to a position outside the existing subscript range; any
 * positions between the existing elements and the new one are set to NULLs.
 * (XXX TODO: allow a corresponding behavior for multidimensional arrays)
 *
 * NOTE: For assignments, we throw an error for invalid subscripts etc,
 * rather than returning a NULL as the fetch operations do.
 */
Datum
array_set_element(Datum arraydatum,
          int nSubscripts,
          int *indx,
          Datum dataValue,
          bool isNull,
          int arraytyplen,
          int elmlen,
          bool elmbyval,
          char elmalign)
{
  ArrayType  *array;
  ArrayType  *newarray;
  int     i,
        ndim,
        dim[MAXDIM],
        lb[MAXDIM],
        offset;
  char     *elt_ptr;
  bool    newhasnulls;
  uint8    *oldnullbitmap;
  int     oldnitems,
        newnitems,
        olddatasize,
        newsize,
        olditemlen,
        newitemlen,
        overheadlen,
        oldoverheadlen,
        addedbefore,
        addedafter,
        lenbefore,
        lenafter;
  uint8   elmalignby = typalign_to_alignby(elmalign);

  if (arraytyplen > 0)
  {
    /*
     * fixed-length arrays -- these are assumed to be 1-d, 0-based. We
     * cannot extend them, either.
     */
    char     *resultarray;

    if (nSubscripts != 1)
      ereport(ERROR,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("wrong number of array subscripts")));

    if (indx[0] < 0 || indx[0] >= arraytyplen / elmlen)
      ereport(ERROR,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("array subscript out of range")));

    if (isNull)
      ereport(ERROR,
          (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
           errmsg("cannot assign null value to an element of a fixed-length array")));

    resultarray = (char *) palloc(arraytyplen);
    memcpy(resultarray, DatumGetPointer(arraydatum), arraytyplen);
    elt_ptr = resultarray + indx[0] * elmlen;
    ArrayCastAndSet(dataValue, elmlen, elmbyval, elmalignby, elt_ptr);
    return PointerGetDatum(resultarray);
  }

  if (nSubscripts <= 0 || nSubscripts > MAXDIM)
    ereport(ERROR,
        (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
         errmsg("wrong number of array subscripts")));

  /* make sure item to be inserted is not toasted */
  if (elmlen == -1 && !isNull)
    dataValue = PointerGetDatum(PG_DETOAST_DATUM(dataValue));

  if (VARATT_IS_EXTERNAL_EXPANDED(DatumGetPointer(arraydatum)))
  {
    /* expanded array: let's do this in a separate function */
    return array_set_element_expanded(arraydatum,
                      nSubscripts,
                      indx,
                      dataValue,
                      isNull,
                      arraytyplen,
                      elmlen,
                      elmbyval,
                      elmalign);
  }

  /* detoast input array if necessary */
  array = DatumGetArrayTypeP(arraydatum);

  ndim = ARR_NDIM(array);

  /*
   * if number of dims is zero, i.e. an empty array, create an array with
   * nSubscripts dimensions, and set the lower bounds to the supplied
   * subscripts
   */
  if (ndim == 0)
  {
    Oid     elmtype = ARR_ELEMTYPE(array);

    for (i = 0; i < nSubscripts; i++)
    {
      dim[i] = 1;
      lb[i] = indx[i];
    }

    return PointerGetDatum(construct_md_array(&dataValue, &isNull,
                          nSubscripts, dim, lb,
                          elmtype,
                          elmlen, elmbyval, elmalign));
  }

  if (ndim != nSubscripts)
    ereport(ERROR,
        (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
         errmsg("wrong number of array subscripts")));

  /* copy dim/lb since we may modify them */
  memcpy(dim, ARR_DIMS(array), ndim * sizeof(int));
  memcpy(lb, ARR_LBOUND(array), ndim * sizeof(int));

  newhasnulls = (ARR_HASNULL(array) || isNull);
  addedbefore = addedafter = 0;

  /*
   * Check subscripts.  We assume the existing subscripts passed
   * ArrayCheckBounds, so that dim[i] + lb[i] can be computed without
   * overflow.  But we must beware of other overflows in our calculations of
   * new dim[] values.
   */
  if (ndim == 1)
  {
    if (indx[0] < lb[0])
    {
      /* addedbefore = lb[0] - indx[0]; */
      /* dim[0] += addedbefore; */
      if (pg_sub_s32_overflow(lb[0], indx[0], &addedbefore) ||
        pg_add_s32_overflow(dim[0], addedbefore, &dim[0]))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxArraySize)));
      lb[0] = indx[0];
      if (addedbefore > 1)
        newhasnulls = true; /* will insert nulls */
    }
    if (indx[0] >= (dim[0] + lb[0]))
    {
      /* addedafter = indx[0] - (dim[0] + lb[0]) + 1; */
      /* dim[0] += addedafter; */
      if (pg_sub_s32_overflow(indx[0], dim[0] + lb[0], &addedafter) ||
        pg_add_s32_overflow(addedafter, 1, &addedafter) ||
        pg_add_s32_overflow(dim[0], addedafter, &dim[0]))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxArraySize)));
      if (addedafter > 1)
        newhasnulls = true; /* will insert nulls */
    }
  }
  else
  {
    /*
     * XXX currently we do not support extending multi-dimensional arrays
     * during assignment
     */
    for (i = 0; i < ndim; i++)
    {
      if (indx[i] < lb[i] ||
        indx[i] >= (dim[i] + lb[i]))
        ereport(ERROR,
            (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
             errmsg("array subscript out of range")));
    }
  }

  /* This checks for overflow of the array dimensions */
  newnitems = ArrayGetNItems(ndim, dim);
  ArrayCheckBounds(ndim, dim, lb);

  /*
   * Compute sizes of items and areas to copy
   */
  if (newhasnulls)
    overheadlen = ARR_OVERHEAD_WITHNULLS(ndim, newnitems);
  else
    overheadlen = ARR_OVERHEAD_NONULLS(ndim);
  oldnitems = ArrayGetNItems(ndim, ARR_DIMS(array));
  oldnullbitmap = ARR_NULLBITMAP(array);
  oldoverheadlen = ARR_DATA_OFFSET(array);
  olddatasize = ARR_SIZE(array) - oldoverheadlen;
  if (addedbefore)
  {
    offset = 0;
    lenbefore = 0;
    olditemlen = 0;
    lenafter = olddatasize;
  }
  else if (addedafter)
  {
    offset = oldnitems;
    lenbefore = olddatasize;
    olditemlen = 0;
    lenafter = 0;
  }
  else
  {
    offset = ArrayGetOffset(nSubscripts, dim, lb, indx);
    elt_ptr = array_seek(ARR_DATA_PTR(array), 0, oldnullbitmap, offset,
               elmlen, elmbyval, elmalign);
    lenbefore = (int) (elt_ptr - ARR_DATA_PTR(array));
    if (array_get_isnull(oldnullbitmap, offset))
      olditemlen = 0;
    else
    {
      olditemlen = att_addlength_pointer(0, elmlen, elt_ptr);
      olditemlen = att_nominal_alignby(olditemlen, elmalignby);
    }
    lenafter = olddatasize - lenbefore - olditemlen;
  }

  if (isNull)
    newitemlen = 0;
  else
  {
    newitemlen = att_addlength_datum(0, elmlen, dataValue);
    newitemlen = att_nominal_alignby(newitemlen, elmalignby);
  }

  newsize = overheadlen + lenbefore + newitemlen + lenafter;

  /*
   * OK, create the new array and fill in header/dimensions
   */
  newarray = (ArrayType *) palloc0(newsize);
  SET_VARSIZE(newarray, newsize);
  newarray->ndim = ndim;
  newarray->dataoffset = newhasnulls ? overheadlen : 0;
  newarray->elemtype = ARR_ELEMTYPE(array);
  memcpy(ARR_DIMS(newarray), dim, ndim * sizeof(int));
  memcpy(ARR_LBOUND(newarray), lb, ndim * sizeof(int));

  /*
   * Fill in data
   */
  memcpy((char *) newarray + overheadlen,
       (char *) array + oldoverheadlen,
       lenbefore);
  if (!isNull)
    ArrayCastAndSet(dataValue, elmlen, elmbyval, elmalignby,
            (char *) newarray + overheadlen + lenbefore);
  memcpy((char *) newarray + overheadlen + lenbefore + newitemlen,
       (char *) array + oldoverheadlen + lenbefore + olditemlen,
       lenafter);

  /*
   * Fill in nulls bitmap if needed
   *
   * Note: it's possible we just replaced the last NULL with a non-NULL, and
   * could get rid of the bitmap.  Seems not worth testing for though.
   */
  if (newhasnulls)
  {
    uint8    *newnullbitmap = ARR_NULLBITMAP(newarray);

    /* palloc0 above already marked any inserted positions as nulls */
    /* Fix the inserted value */
    if (addedafter)
      array_set_isnull(newnullbitmap, newnitems - 1, isNull);
    else
      array_set_isnull(newnullbitmap, offset, isNull);
    /* Fix the copied range(s) */
    if (addedbefore)
      array_bitmap_copy(newnullbitmap, addedbefore,
                oldnullbitmap, 0,
                oldnitems);
    else
    {
      array_bitmap_copy(newnullbitmap, 0,
                oldnullbitmap, 0,
                offset);
      if (addedafter == 0)
        array_bitmap_copy(newnullbitmap, offset + 1,
                  oldnullbitmap, offset + 1,
                  oldnitems - offset - 1);
    }
  }

  return PointerGetDatum(newarray);
}

/*
 * Implementation of array_set_element() for an expanded array
 *
 * Note: as with any operation on a read/write expanded object, we must
 * take pains not to leave the object in a corrupt state if we fail partway
 * through.
 */
static Datum
array_set_element_expanded(Datum arraydatum,
               int nSubscripts, int *indx,
               Datum dataValue, bool isNull,
               int arraytyplen,
               int elmlen, bool elmbyval, char elmalign)
{
  ExpandedArrayHeader *eah;
  Datum    *dvalues;
  bool     *dnulls;
  int     i,
        ndim,
        dim[MAXDIM],
        lb[MAXDIM],
        offset;
  bool    dimschanged,
        newhasnulls;
  int     addedbefore,
        addedafter;
  char     *oldValue;

  /* Convert to R/W object if not so already */
  eah = DatumGetExpandedArray(arraydatum);

  /* Sanity-check caller's info against object; we don't use it otherwise */
  Assert(arraytyplen == -1);
  Assert(elmlen == eah->typlen);
  Assert(elmbyval == eah->typbyval);
  Assert(elmalign == eah->typalign);

  /*
   * Copy dimension info into local storage.  This allows us to modify the
   * dimensions if needed, while not messing up the expanded value if we
   * fail partway through.
   */
  ndim = eah->ndims;
  Assert(ndim >= 0 && ndim <= MAXDIM);
  memcpy(dim, eah->dims, ndim * sizeof(int));
  memcpy(lb, eah->lbound, ndim * sizeof(int));
  dimschanged = false;

  /*
   * if number of dims is zero, i.e. an empty array, create an array with
   * nSubscripts dimensions, and set the lower bounds to the supplied
   * subscripts.
   */
  if (ndim == 0)
  {
    /*
     * Allocate adequate space for new dimension info.  This is harmless
     * if we fail later.
     */
    Assert(nSubscripts > 0 && nSubscripts <= MAXDIM);
    eah->dims = (int *) MemoryContextAllocZero(eah->hdr.eoh_context,
                           nSubscripts * sizeof(int));
    eah->lbound = (int *) MemoryContextAllocZero(eah->hdr.eoh_context,
                           nSubscripts * sizeof(int));

    /* Update local copies of dimension info */
    ndim = nSubscripts;
    for (i = 0; i < nSubscripts; i++)
    {
      dim[i] = 0;
      lb[i] = indx[i];
    }
    dimschanged = true;
  }
  else if (ndim != nSubscripts)
    ereport(ERROR,
        (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
         errmsg("wrong number of array subscripts")));

  /*
   * Deconstruct array if we didn't already.  (Someday maybe add a special
   * case path for fixed-length, no-nulls cases, where we can overwrite an
   * element in place without ever deconstructing.  But today is not that
   * day.)
   */
  deconstruct_expanded_array(eah);

  /*
   * Copy new element into array's context, if needed (we assume it's
   * already detoasted, so no junk should be created).  Doing this before
   * we've made any significant changes ensures that our behavior is sane
   * even when the source is a reference to some element of this same array.
   * If we fail further down, this memory is leaked, but that's reasonably
   * harmless.
   */
  if (!eah->typbyval && !isNull)
  {
    MemoryContext oldcxt = MemoryContextSwitchTo(eah->hdr.eoh_context);

    dataValue = datumCopy(dataValue, false, eah->typlen);
    MemoryContextSwitchTo(oldcxt);
  }

  dvalues = eah->dvalues;
  dnulls = eah->dnulls;

  newhasnulls = ((dnulls != NULL) || isNull);
  addedbefore = addedafter = 0;

  /*
   * Check subscripts (this logic must match array_set_element).  We assume
   * the existing subscripts passed ArrayCheckBounds, so that dim[i] + lb[i]
   * can be computed without overflow.  But we must beware of other
   * overflows in our calculations of new dim[] values.
   */
  if (ndim == 1)
  {
    if (indx[0] < lb[0])
    {
      /* addedbefore = lb[0] - indx[0]; */
      /* dim[0] += addedbefore; */
      if (pg_sub_s32_overflow(lb[0], indx[0], &addedbefore) ||
        pg_add_s32_overflow(dim[0], addedbefore, &dim[0]))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxArraySize)));
      lb[0] = indx[0];
      dimschanged = true;
      if (addedbefore > 1)
        newhasnulls = true; /* will insert nulls */
    }
    if (indx[0] >= (dim[0] + lb[0]))
    {
      /* addedafter = indx[0] - (dim[0] + lb[0]) + 1; */
      /* dim[0] += addedafter; */
      if (pg_sub_s32_overflow(indx[0], dim[0] + lb[0], &addedafter) ||
        pg_add_s32_overflow(addedafter, 1, &addedafter) ||
        pg_add_s32_overflow(dim[0], addedafter, &dim[0]))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxArraySize)));
      dimschanged = true;
      if (addedafter > 1)
        newhasnulls = true; /* will insert nulls */
    }
  }
  else
  {
    /*
     * XXX currently we do not support extending multi-dimensional arrays
     * during assignment
     */
    for (i = 0; i < ndim; i++)
    {
      if (indx[i] < lb[i] ||
        indx[i] >= (dim[i] + lb[i]))
        ereport(ERROR,
            (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
             errmsg("array subscript out of range")));
    }
  }

  /* Check for overflow of the array dimensions */
  if (dimschanged)
  {
    (void) ArrayGetNItems(ndim, dim);
    ArrayCheckBounds(ndim, dim, lb);
  }

  /* Now we can calculate linear offset of target item in array */
  offset = ArrayGetOffset(nSubscripts, dim, lb, indx);

  /* Physically enlarge existing dvalues/dnulls arrays if needed */
  if (dim[0] > eah->dvalueslen)
  {
    /* We want some extra space if we're enlarging */
    int     newlen = dim[0] + dim[0] / 8;

    newlen = Max(newlen, dim[0]); /* integer overflow guard */
    eah->dvalues = dvalues = (Datum *)
      repalloc(dvalues, newlen * sizeof(Datum));
    if (dnulls)
      eah->dnulls = dnulls = (bool *)
        repalloc(dnulls, newlen * sizeof(bool));
    eah->dvalueslen = newlen;
  }

  /*
   * If we need a nulls bitmap and don't already have one, create it, being
   * sure to mark all existing entries as not null.
   */
  if (newhasnulls && dnulls == NULL)
    eah->dnulls = dnulls = (bool *)
      MemoryContextAllocZero(eah->hdr.eoh_context,
                   eah->dvalueslen * sizeof(bool));

  /*
   * We now have all the needed space allocated, so we're ready to make
   * irreversible changes.  Be very wary of allowing failure below here.
   */

  /* Flattened value will no longer represent array accurately */
  eah->fvalue = NULL;
  /* And we don't know the flattened size either */
  eah->flat_size = 0;

  /* Update dimensionality info if needed */
  if (dimschanged)
  {
    eah->ndims = ndim;
    memcpy(eah->dims, dim, ndim * sizeof(int));
    memcpy(eah->lbound, lb, ndim * sizeof(int));
  }

  /* Reposition items if needed, and fill addedbefore items with nulls */
  if (addedbefore > 0)
  {
    memmove(dvalues + addedbefore, dvalues, eah->nelems * sizeof(Datum));
    for (i = 0; i < addedbefore; i++)
      dvalues[i] = (Datum) 0;
    if (dnulls)
    {
      memmove(dnulls + addedbefore, dnulls, eah->nelems * sizeof(bool));
      for (i = 0; i < addedbefore; i++)
        dnulls[i] = true;
    }
    eah->nelems += addedbefore;
  }

  /* fill addedafter items with nulls */
  if (addedafter > 0)
  {
    for (i = 0; i < addedafter; i++)
      dvalues[eah->nelems + i] = (Datum) 0;
    if (dnulls)
    {
      for (i = 0; i < addedafter; i++)
        dnulls[eah->nelems + i] = true;
    }
    eah->nelems += addedafter;
  }

  /* Grab old element value for pfree'ing, if needed. */
  if (!eah->typbyval && (dnulls == NULL || !dnulls[offset]))
    oldValue = (char *) DatumGetPointer(dvalues[offset]);
  else
    oldValue = NULL;

  /* And finally we can insert the new element. */
  dvalues[offset] = dataValue;
  if (dnulls)
    dnulls[offset] = isNull;

  /*
   * Free old element if needed; this keeps repeated element replacements
   * from bloating the array's storage.  If the pfree somehow fails, it
   * won't corrupt the array.
   */
  if (oldValue)
  {
    /* Don't try to pfree a part of the original flat array */
    if (oldValue < eah->fstartptr || oldValue >= eah->fendptr)
      pfree(oldValue);
  }

  /* Done, return standard TOAST pointer for object */
  return EOHPGetRWDatum(&eah->hdr);
}

/*
 * array_set_slice :
 *      This routine sets the value of a range of array locations (specified
 *      by upper and lower subscript values) to new values passed as
 *      another array.
 *
 * This handles both ordinary varlena arrays and fixed-length arrays.
 *
 * Inputs:
 *  arraydatum: the initial array object (mustn't be NULL)
 *  nSubscripts: number of subscripts supplied (must be same for upper/lower)
 *  upperIndx[]: the upper subscript values
 *  lowerIndx[]: the lower subscript values
 *  upperProvided[]: true for provided upper subscript values
 *  lowerProvided[]: true for provided lower subscript values
 *  srcArrayDatum: the source for the inserted values
 *  isNull: indicates whether srcArrayDatum is NULL
 *  arraytyplen: pg_type.typlen for the array type
 *  elmlen: pg_type.typlen for the array's element type
 *  elmbyval: pg_type.typbyval for the array's element type
 *  elmalign: pg_type.typalign for the array's element type
 *
 * Result:
 *      A new array is returned, just like the old except for the
 *      modified range.  The original array object is not changed.
 *
 * Omitted upper and lower subscript values are replaced by the corresponding
 * array bound.
 *
 * For one-dimensional arrays only, we allow the array to be extended
 * by assigning to positions outside the existing subscript range; any
 * positions between the existing elements and the new ones are set to NULLs.
 * (XXX TODO: allow a corresponding behavior for multidimensional arrays)
 *
 * NOTE: we assume it is OK to scribble on the provided index arrays
 * lowerIndx[] and upperIndx[]; also, these arrays must be of size MAXDIM
 * even when nSubscripts is less.  These are generally just temporaries.
 *
 * NOTE: For assignments, we throw an error for silly subscripts etc,
 * rather than returning a NULL or empty array as the fetch operations do.
 */
Datum
array_set_slice(Datum arraydatum,
        int nSubscripts,
        int *upperIndx,
        int *lowerIndx,
        bool *upperProvided,
        bool *lowerProvided,
        Datum srcArrayDatum,
        bool isNull,
        int arraytyplen,
        int elmlen,
        bool elmbyval,
        char elmalign)
{
  ArrayType  *array;
  ArrayType  *srcArray;
  ArrayType  *newarray;
  int     i,
        ndim,
        dim[MAXDIM],
        lb[MAXDIM],
        span[MAXDIM];
  bool    newhasnulls;
  int     nitems,
        nsrcitems,
        olddatasize,
        newsize,
        olditemsize,
        newitemsize,
        overheadlen,
        oldoverheadlen,
        addedbefore,
        addedafter,
        lenbefore,
        lenafter,
        itemsbefore,
        itemsafter,
        nolditems;

  /* Currently, assignment from a NULL source array is a no-op */
  if (isNull)
    return arraydatum;

  if (arraytyplen > 0)
  {
    /*
     * fixed-length arrays -- not got round to doing this...
     */
    ereport(ERROR,
        (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
         errmsg("updates on slices of fixed-length arrays not implemented")));
  }

  /* detoast arrays if necessary */
  array = DatumGetArrayTypeP(arraydatum);
  srcArray = DatumGetArrayTypeP(srcArrayDatum);

  /* note: we assume srcArray contains no toasted elements */

  ndim = ARR_NDIM(array);

  /*
   * if number of dims is zero, i.e. an empty array, create an array with
   * nSubscripts dimensions, and set the upper and lower bounds to the
   * supplied subscripts
   */
  if (ndim == 0)
  {
    Datum    *dvalues;
    bool     *dnulls;
    int     nelems;
    Oid     elmtype = ARR_ELEMTYPE(array);

    deconstruct_array(srcArray, elmtype, elmlen, elmbyval, elmalign,
              &dvalues, &dnulls, &nelems);

    for (i = 0; i < nSubscripts; i++)
    {
      if (!upperProvided[i] || !lowerProvided[i])
        ereport(ERROR,
            (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
             errmsg("array slice subscript must provide both boundaries"),
             errdetail("When assigning to a slice of an empty array value,"
                   " slice boundaries must be fully specified.")));

      /* compute "upperIndx[i] - lowerIndx[i] + 1", detecting overflow */
      if (pg_sub_s32_overflow(upperIndx[i], lowerIndx[i], &dim[i]) ||
        pg_add_s32_overflow(dim[i], 1, &dim[i]))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxArraySize)));

      lb[i] = lowerIndx[i];
    }

    /* complain if too few source items; we ignore extras, however */
    if (nelems < ArrayGetNItems(nSubscripts, dim))
      ereport(ERROR,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("source array too small")));

    return PointerGetDatum(construct_md_array(dvalues, dnulls, nSubscripts,
                          dim, lb, elmtype,
                          elmlen, elmbyval, elmalign));
  }

  if (ndim < nSubscripts || ndim <= 0 || ndim > MAXDIM)
    ereport(ERROR,
        (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
         errmsg("wrong number of array subscripts")));

  /* copy dim/lb since we may modify them */
  memcpy(dim, ARR_DIMS(array), ndim * sizeof(int));
  memcpy(lb, ARR_LBOUND(array), ndim * sizeof(int));

  newhasnulls = (ARR_HASNULL(array) || ARR_HASNULL(srcArray));
  addedbefore = addedafter = 0;

  /*
   * Check subscripts.  We assume the existing subscripts passed
   * ArrayCheckBounds, so that dim[i] + lb[i] can be computed without
   * overflow.  But we must beware of other overflows in our calculations of
   * new dim[] values.
   */
  if (ndim == 1)
  {
    Assert(nSubscripts == 1);
    if (!lowerProvided[0])
      lowerIndx[0] = lb[0];
    if (!upperProvided[0])
      upperIndx[0] = dim[0] + lb[0] - 1;
    if (lowerIndx[0] > upperIndx[0])
      ereport(ERROR,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("upper bound cannot be less than lower bound")));
    if (lowerIndx[0] < lb[0])
    {
      /* addedbefore = lb[0] - lowerIndx[0]; */
      /* dim[0] += addedbefore; */
      if (pg_sub_s32_overflow(lb[0], lowerIndx[0], &addedbefore) ||
        pg_add_s32_overflow(dim[0], addedbefore, &dim[0]))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxArraySize)));
      lb[0] = lowerIndx[0];
      if (addedbefore > 1)
        newhasnulls = true; /* will insert nulls */
    }
    if (upperIndx[0] >= (dim[0] + lb[0]))
    {
      /* addedafter = upperIndx[0] - (dim[0] + lb[0]) + 1; */
      /* dim[0] += addedafter; */
      if (pg_sub_s32_overflow(upperIndx[0], dim[0] + lb[0], &addedafter) ||
        pg_add_s32_overflow(addedafter, 1, &addedafter) ||
        pg_add_s32_overflow(dim[0], addedafter, &dim[0]))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxArraySize)));
      if (addedafter > 1)
        newhasnulls = true; /* will insert nulls */
    }
  }
  else
  {
    /*
     * XXX currently we do not support extending multi-dimensional arrays
     * during assignment
     */
    for (i = 0; i < nSubscripts; i++)
    {
      if (!lowerProvided[i])
        lowerIndx[i] = lb[i];
      if (!upperProvided[i])
        upperIndx[i] = dim[i] + lb[i] - 1;
      if (lowerIndx[i] > upperIndx[i])
        ereport(ERROR,
            (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
             errmsg("upper bound cannot be less than lower bound")));
      if (lowerIndx[i] < lb[i] ||
        upperIndx[i] >= (dim[i] + lb[i]))
        ereport(ERROR,
            (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
             errmsg("array subscript out of range")));
    }
    /* fill any missing subscript positions with full array range */
    for (; i < ndim; i++)
    {
      lowerIndx[i] = lb[i];
      upperIndx[i] = dim[i] + lb[i] - 1;
      if (lowerIndx[i] > upperIndx[i])
        ereport(ERROR,
            (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
             errmsg("upper bound cannot be less than lower bound")));
    }
  }

  /* Do this mainly to check for overflow */
  nitems = ArrayGetNItems(ndim, dim);
  ArrayCheckBounds(ndim, dim, lb);

  /*
   * Make sure source array has enough entries.  Note we ignore the shape of
   * the source array and just read entries serially.
   */
  mda_get_range(ndim, span, lowerIndx, upperIndx);
  nsrcitems = ArrayGetNItems(ndim, span);
  if (nsrcitems > ArrayGetNItems(ARR_NDIM(srcArray), ARR_DIMS(srcArray)))
    ereport(ERROR,
        (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
         errmsg("source array too small")));

  /*
   * Compute space occupied by new entries, space occupied by replaced
   * entries, and required space for new array.
   */
  if (newhasnulls)
    overheadlen = ARR_OVERHEAD_WITHNULLS(ndim, nitems);
  else
    overheadlen = ARR_OVERHEAD_NONULLS(ndim);
  newitemsize = array_nelems_size(ARR_DATA_PTR(srcArray), 0,
                  ARR_NULLBITMAP(srcArray), nsrcitems,
                  elmlen, elmbyval, elmalign);
  oldoverheadlen = ARR_DATA_OFFSET(array);
  olddatasize = ARR_SIZE(array) - oldoverheadlen;
  if (ndim > 1)
  {
    /*
     * here we do not need to cope with extension of the array; it would
     * be a lot more complicated if we had to do so...
     */
    olditemsize = array_slice_size(ARR_DATA_PTR(array),
                     ARR_NULLBITMAP(array),
                     ndim, dim, lb,
                     lowerIndx, upperIndx,
                     elmlen, elmbyval, elmalign);
    lenbefore = lenafter = 0; /* keep compiler quiet */
    itemsbefore = itemsafter = nolditems = 0;
  }
  else
  {
    /*
     * here we must allow for possibility of slice larger than orig array
     * and/or not adjacent to orig array subscripts
     */
    int     oldlb = ARR_LBOUND(array)[0];
    int     oldub = oldlb + ARR_DIMS(array)[0] - 1;
    int     slicelb = Max(oldlb, lowerIndx[0]);
    int     sliceub = Min(oldub, upperIndx[0]);
    char     *oldarraydata = ARR_DATA_PTR(array);
    uint8    *oldarraybitmap = ARR_NULLBITMAP(array);

    /* count/size of old array entries that will go before the slice */
    itemsbefore = Min(slicelb, oldub + 1) - oldlb;
    lenbefore = array_nelems_size(oldarraydata, 0, oldarraybitmap,
                    itemsbefore,
                    elmlen, elmbyval, elmalign);
    /* count/size of old array entries that will be replaced by slice */
    if (slicelb > sliceub)
    {
      nolditems = 0;
      olditemsize = 0;
    }
    else
    {
      nolditems = sliceub - slicelb + 1;
      olditemsize = array_nelems_size(oldarraydata + lenbefore,
                      itemsbefore, oldarraybitmap,
                      nolditems,
                      elmlen, elmbyval, elmalign);
    }
    /* count/size of old array entries that will go after the slice */
    itemsafter = oldub + 1 - Max(sliceub + 1, oldlb);
    lenafter = olddatasize - lenbefore - olditemsize;
  }

  newsize = overheadlen + olddatasize - olditemsize + newitemsize;

  newarray = (ArrayType *) palloc0(newsize);
  SET_VARSIZE(newarray, newsize);
  newarray->ndim = ndim;
  newarray->dataoffset = newhasnulls ? overheadlen : 0;
  newarray->elemtype = ARR_ELEMTYPE(array);
  memcpy(ARR_DIMS(newarray), dim, ndim * sizeof(int));
  memcpy(ARR_LBOUND(newarray), lb, ndim * sizeof(int));

  if (ndim > 1)
  {
    /*
     * here we do not need to cope with extension of the array; it would
     * be a lot more complicated if we had to do so...
     */
    array_insert_slice(newarray, array, srcArray,
               ndim, dim, lb,
               lowerIndx, upperIndx,
               elmlen, elmbyval, elmalign);
  }
  else
  {
    /* fill in data */
    memcpy((char *) newarray + overheadlen,
         (char *) array + oldoverheadlen,
         lenbefore);
    memcpy((char *) newarray + overheadlen + lenbefore,
         ARR_DATA_PTR(srcArray),
         newitemsize);
    memcpy((char *) newarray + overheadlen + lenbefore + newitemsize,
         (char *) array + oldoverheadlen + lenbefore + olditemsize,
         lenafter);
    /* fill in nulls bitmap if needed */
    if (newhasnulls)
    {
      uint8    *newnullbitmap = ARR_NULLBITMAP(newarray);
      uint8    *oldnullbitmap = ARR_NULLBITMAP(array);

      /* palloc0 above already marked any inserted positions as nulls */
      array_bitmap_copy(newnullbitmap, addedbefore,
                oldnullbitmap, 0,
                itemsbefore);
      array_bitmap_copy(newnullbitmap, lowerIndx[0] - lb[0],
                ARR_NULLBITMAP(srcArray), 0,
                nsrcitems);
      array_bitmap_copy(newnullbitmap, addedbefore + itemsbefore + nolditems,
                oldnullbitmap, itemsbefore + nolditems,
                itemsafter);
    }
  }

  return PointerGetDatum(newarray);
}

/*
 * array_ref : backwards compatibility wrapper for array_get_element
 *
 * This only works for detoasted/flattened varlena arrays, since the array
 * argument is declared as "ArrayType *".  However there's enough code like
 * that to justify preserving this API.
 */
Datum
array_ref(ArrayType *array, int nSubscripts, int *indx,
      int arraytyplen, int elmlen, bool elmbyval, char elmalign,
      bool *isNull)
{
  return array_get_element(PointerGetDatum(array), nSubscripts, indx,
               arraytyplen, elmlen, elmbyval, elmalign,
               isNull);
}

/*
 * array_set : backwards compatibility wrapper for array_set_element
 *
 * This only works for detoasted/flattened varlena arrays, since the array
 * argument and result are declared as "ArrayType *".  However there's enough
 * code like that to justify preserving this API.
 */
ArrayType *
array_set(ArrayType *array, int nSubscripts, int *indx,
      Datum dataValue, bool isNull,
      int arraytyplen, int elmlen, bool elmbyval, char elmalign)
{
  return DatumGetArrayTypeP(array_set_element(PointerGetDatum(array),
                        nSubscripts, indx,
                        dataValue, isNull,
                        arraytyplen,
                        elmlen, elmbyval, elmalign));
}

/*
 * array_map()
 *
 * Map an array through an arbitrary expression.  Return a new array with
 * the same dimensions and each source element transformed by the given,
 * already-compiled expression.  Each source element is placed in the
 * innermost_caseval/innermost_casenull fields of the ExprState.
 *
 * Parameters are:
 * * arrayd: Datum representing array argument.
 * * exprstate: ExprState representing the per-element transformation.
 * * econtext: context for expression evaluation.
 * * retType: OID of element type of output array.  This must be the same as,
 *   or binary-compatible with, the result type of the expression.  It might
 *   be different from the input array's element type.
 * * amstate: workspace for array_map.  Must be zeroed by caller before
 *   first call, and not touched after that.
 *
 * It is legitimate to pass a freshly-zeroed ArrayMapState on each call,
 * but better performance can be had if the state can be preserved across
 * a series of calls.
 *
 * NB: caller must assure that input array is not NULL.  NULL elements in
 * the array are OK however.
 * NB: caller should be running in econtext's per-tuple memory context.
 */
Datum
array_map(Datum arrayd,
      ExprState *exprstate, ExprContext *econtext,
      Oid retType, ArrayMapState *amstate)
{
  AnyArrayType *v = DatumGetAnyArrayP(arrayd);
  ArrayType  *result;
  Datum    *values;
  bool     *nulls;
  int      *dim;
  int     ndim;
  int     nitems;
  int     i;
  int32   nbytes = 0;
  int32   dataoffset;
  bool    hasnulls;
  Oid     inpType;
  int     inp_typlen;
  bool    inp_typbyval;
  char    inp_typalign;
  int     typlen;
  bool    typbyval;
  char    typalign;
  uint8   typalignby;
  array_iter  iter;
  ArrayMetaState *inp_extra;
  ArrayMetaState *ret_extra;
  Datum    *transform_source = exprstate->innermost_caseval;
  bool     *transform_source_isnull = exprstate->innermost_casenull;

  inpType = AARR_ELEMTYPE(v);
  ndim = AARR_NDIM(v);
  dim = AARR_DIMS(v);
  nitems = ArrayGetNItems(ndim, dim);

  /* Check for empty array */
  if (nitems <= 0)
  {
    /* Return empty array */
    return PointerGetDatum(construct_empty_array(retType));
  }

  /*
   * We arrange to look up info about input and return element types only
   * once per series of calls, assuming the element type doesn't change
   * underneath us.
   */
  inp_extra = &amstate->inp_extra;
  ret_extra = &amstate->ret_extra;

  if (inp_extra->element_type != inpType)
  {
    get_typlenbyvalalign(inpType,
               &inp_extra->typlen,
               &inp_extra->typbyval,
               &inp_extra->typalign);
    inp_extra->element_type = inpType;
  }
  inp_typlen = inp_extra->typlen;
  inp_typbyval = inp_extra->typbyval;
  inp_typalign = inp_extra->typalign;

  if (ret_extra->element_type != retType)
  {
    get_typlenbyvalalign(retType,
               &ret_extra->typlen,
               &ret_extra->typbyval,
               &ret_extra->typalign);
    ret_extra->element_type = retType;
  }
  typlen = ret_extra->typlen;
  typbyval = ret_extra->typbyval;
  typalign = ret_extra->typalign;
  typalignby = typalign_to_alignby(typalign);

  /* Allocate temporary arrays for new values */
  values = (Datum *) palloc(nitems * sizeof(Datum));
  nulls = (bool *) palloc(nitems * sizeof(bool));

  /* Loop over source data */
  array_iter_setup(&iter, v, inp_typlen, inp_typbyval, inp_typalign);
  hasnulls = false;

  for (i = 0; i < nitems; i++)
  {
    /* Get source element, checking for NULL */
    *transform_source =
      array_iter_next(&iter, transform_source_isnull, i);

    /* Apply the given expression to source element */
    values[i] = ExecEvalExpr(exprstate, econtext, &nulls[i]);

    if (nulls[i])
      hasnulls = true;
    else
    {
      /* Ensure data is not toasted */
      if (typlen == -1)
        values[i] = PointerGetDatum(PG_DETOAST_DATUM(values[i]));
      /* Update total result size */
      nbytes = att_addlength_datum(nbytes, typlen, values[i]);
      nbytes = att_nominal_alignby(nbytes, typalignby);
      /* check for overflow of total request */
      if (!AllocSizeIsValid(nbytes))
        ereport(ERROR,
            (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
             errmsg("array size exceeds the maximum allowed (%zu)",
                MaxAllocSize)));
    }
  }

  /* Allocate and fill the result array */
  if (hasnulls)
  {
    dataoffset = ARR_OVERHEAD_WITHNULLS(ndim, nitems);
    nbytes += dataoffset;
  }
  else
  {
    dataoffset = 0;     /* marker for no null bitmap */
    nbytes += ARR_OVERHEAD_NONULLS(ndim);
  }
  result = (ArrayType *) palloc0(nbytes);
  SET_VARSIZE(result, nbytes);
  result->ndim = ndim;
  result->dataoffset = dataoffset;
  result->elemtype = retType;
  memcpy(ARR_DIMS(result), AARR_DIMS(v), ndim * sizeof(int));
  memcpy(ARR_LBOUND(result), AARR_LBOUND(v), ndim * sizeof(int));

  CopyArrayEls(result,
         values, nulls, nitems,
         typlen, typbyval, typalign,
         false);

  /*
   * Note: do not risk trying to pfree the results of the called expression
   */
  pfree(values);
  pfree(nulls);

  return PointerGetDatum(result);
}

/*
 * construct_array  --- simple method for constructing an array object
 *
 * elems: array of Datum items to become the array contents
 *      (NULL element values are not supported).
 * nelems: number of items
 * elmtype, elmlen, elmbyval, elmalign: info for the datatype of the items
 *
 * A palloc'd 1-D array object is constructed and returned.  Note that
 * elem values will be copied into the object even if pass-by-ref type.
 * Also note the result will be 0-D not 1-D if nelems = 0.
 *
 * NOTE: it would be cleaner to look up the elmlen/elmbval/elmalign info
 * from the system catalogs, given the elmtype.  However, the caller is
 * in a better position to cache this info across multiple uses, or even
 * to hard-wire values if the element type is hard-wired.
 */
ArrayType *
construct_array(Datum *elems, int nelems,
        Oid elmtype,
        int elmlen, bool elmbyval, char elmalign)
{
  int     dims[1];
  int     lbs[1];

  dims[0] = nelems;
  lbs[0] = 1;

  return construct_md_array(elems, NULL, 1, dims, lbs,
                elmtype, elmlen, elmbyval, elmalign);
}

/*
 * Like construct_array(), where elmtype must be a built-in type, and
 * elmlen/elmbyval/elmalign is looked up from hardcoded data.  This is often
 * useful when manipulating arrays from/for system catalogs.
 */
ArrayType *
construct_array_builtin(Datum *elems, int nelems, Oid elmtype)
{
  int     elmlen;
  bool    elmbyval;
  char    elmalign;

  switch (elmtype)
  {
    case CHAROID:
      elmlen = 1;
      elmbyval = true;
      elmalign = TYPALIGN_CHAR;
      break;

    case CSTRINGOID:
      elmlen = -2;
      elmbyval = false;
      elmalign = TYPALIGN_CHAR;
      break;

    case FLOAT4OID:
      elmlen = sizeof(float4);
      elmbyval = true;
      elmalign = TYPALIGN_INT;
      break;

    case FLOAT8OID:
      elmlen = sizeof(float8);
      elmbyval = true;
      elmalign = TYPALIGN_DOUBLE;
      break;

    case INT2OID:
      elmlen = sizeof(int16);
      elmbyval = true;
      elmalign = TYPALIGN_SHORT;
      break;

    case INT4OID:
      elmlen = sizeof(int32);
      elmbyval = true;
      elmalign = TYPALIGN_INT;
      break;

    case INT8OID:
      elmlen = sizeof(int64);
      elmbyval = true;
      elmalign = TYPALIGN_DOUBLE;
      break;

    case NAMEOID:
      elmlen = NAMEDATALEN;
      elmbyval = false;
      elmalign = TYPALIGN_CHAR;
      break;

    case OIDOID:
    case REGTYPEOID:
      elmlen = sizeof(Oid);
      elmbyval = true;
      elmalign = TYPALIGN_INT;
      break;

    case TEXTOID:
      elmlen = -1;
      elmbyval = false;
      elmalign = TYPALIGN_INT;
      break;

    case TIDOID:
      elmlen = sizeof(ItemPointerData);
      elmbyval = false;
      elmalign = TYPALIGN_SHORT;
      break;

    case XIDOID:
      elmlen = sizeof(TransactionId);
      elmbyval = true;
      elmalign = TYPALIGN_INT;
      break;

    default:
      elog(ERROR, "type %u not supported by construct_array_builtin()", elmtype);
      /* keep compiler quiet */
      elmlen = 0;
      elmbyval = false;
      elmalign = 0;
  }

  return construct_array(elems, nelems, elmtype, elmlen, elmbyval, elmalign);
}

/*
 * construct_md_array --- simple method for constructing an array object
 *              with arbitrary dimensions and possible NULLs
 *
 * elems: array of Datum items to become the array contents
 * nulls: array of is-null flags (can be NULL if no nulls)
 * ndims: number of dimensions
 * dims: integer array with size of each dimension
 * lbs: integer array with lower bound of each dimension
 * elmtype, elmlen, elmbyval, elmalign: info for the datatype of the items
 *
 * A palloc'd ndims-D array object is constructed and returned.  Note that
 * elem values will be copied into the object even if pass-by-ref type.
 * Also note the result will be 0-D not ndims-D if any dims[i] = 0.
 *
 * NOTE: it would be cleaner to look up the elmlen/elmbval/elmalign info
 * from the system catalogs, given the elmtype.  However, the caller is
 * in a better position to cache this info across multiple uses, or even
 * to hard-wire values if the element type is hard-wired.
 */
ArrayType *
construct_md_array(Datum *elems,
           bool *nulls,
           int ndims,
           int *dims,
           int *lbs,
           Oid elmtype, int elmlen, bool elmbyval, char elmalign)
{
  ArrayType  *result;
  bool    hasnulls;
  int32   nbytes;
  int32   dataoffset;
  int     i;
  int     nelems;
  uint8   elmalignby = typalign_to_alignby(elmalign);

  if (ndims < 0)       /* we do allow zero-dimension arrays */
    ereport(ERROR,
        (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
         errmsg("invalid number of dimensions: %d", ndims)));
  if (ndims > MAXDIM)
    ereport(ERROR,
        (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
         errmsg("number of array dimensions (%d) exceeds the maximum allowed (%d)",
            ndims, MAXDIM)));

  /* This checks for overflow of the array dimensions */
  nelems = ArrayGetNItems(ndims, dims);
  ArrayCheckBounds(ndims, dims, lbs);

  /* if ndims <= 0 or any dims[i] == 0, return empty array */
  if (nelems <= 0)
    return construct_empty_array(elmtype);

  /* compute required space */
  nbytes = 0;
  hasnulls = false;
  for (i = 0; i < nelems; i++)
  {
    if (nulls && nulls[i])
    {
      hasnulls = true;
      continue;
    }
    /* make sure data is not toasted */
    if (elmlen == -1)
      elems[i] = PointerGetDatum(PG_DETOAST_DATUM(elems[i]));
    nbytes = att_addlength_datum(nbytes, elmlen, elems[i]);
    nbytes = att_nominal_alignby(nbytes, elmalignby);
    /* check for overflow of total request */
    if (!AllocSizeIsValid(nbytes))
      ereport(ERROR,
          (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
           errmsg("array size exceeds the maximum allowed (%zu)",
              MaxAllocSize)));
  }

  /* Allocate and initialize result array */
  if (hasnulls)
  {
    dataoffset = ARR_OVERHEAD_WITHNULLS(ndims, nelems);
    nbytes += dataoffset;
  }
  else
  {
    dataoffset = 0;     /* marker for no null bitmap */
    nbytes += ARR_OVERHEAD_NONULLS(ndims);
  }
  result = (ArrayType *) palloc0(nbytes);
  SET_VARSIZE(result, nbytes);
  result->ndim = ndims;
  result->dataoffset = dataoffset;
  result->elemtype = elmtype;
  memcpy(ARR_DIMS(result), dims, ndims * sizeof(int));
  memcpy(ARR_LBOUND(result), lbs, ndims * sizeof(int));

  CopyArrayEls(result,
         elems, nulls, nelems,
         elmlen, elmbyval, elmalign,
         false);

  return result;
}

/*
 * construct_empty_array  --- make a zero-dimensional array of given type
 */
ArrayType *
construct_empty_array(Oid elmtype)
{
  ArrayType  *result;

  result = palloc0_object(ArrayType);
  SET_VARSIZE(result, sizeof(ArrayType));
  result->ndim = 0;
  result->dataoffset = 0;
  result->elemtype = elmtype;
  return result;
}

/*
 * construct_empty_expanded_array: make an empty expanded array
 * given only type information.  (metacache can be NULL if not needed.)
 */
ExpandedArrayHeader *
construct_empty_expanded_array(Oid element_type,
                 MemoryContext parentcontext,
                 ArrayMetaState *metacache)
{
  ArrayType  *array = construct_empty_array(element_type);
  Datum   d;

  d = expand_array(PointerGetDatum(array), parentcontext, metacache);
  pfree(array);
  return (ExpandedArrayHeader *) DatumGetEOHP(d);
}

/*
 * deconstruct_array  --- simple method for extracting data from an array
 *
 * array: array object to examine (must not be NULL)
 * elmtype, elmlen, elmbyval, elmalign: info for the datatype of the items
 * elemsp: return value, set to point to palloc'd array of Datum values
 * nullsp: return value, set to point to palloc'd array of isnull markers
 * nelemsp: return value, set to number of extracted values
 *
 * The caller may pass nullsp == NULL if it does not support NULLs in the
 * array.  Note that this produces a very uninformative error message,
 * so do it only in cases where a NULL is really not expected.
 *
 * If array elements are pass-by-ref data type, the returned Datums will
 * be pointers into the array object.
 *
 * NOTE: it would be cleaner to look up the elmlen/elmbval/elmalign info
 * from the system catalogs, given the elmtype.  However, the caller is
 * in a better position to cache this info across multiple uses, or even
 * to hard-wire values if the element type is hard-wired.
 */
void
deconstruct_array(const ArrayType *array,
          Oid elmtype,
          int elmlen, bool elmbyval, char elmalign,
          Datum **elemsp, bool **nullsp, int *nelemsp)
{
  Datum    *elems;
  bool     *nulls;
  int     nelems;
  char     *p;
  uint8    *bitmap;
  int     bitmask;
  int     i;
  uint8   elmalignby = typalign_to_alignby(elmalign);

  Assert(ARR_ELEMTYPE(array) == elmtype);

  nelems = ArrayGetNItems(ARR_NDIM(array), ARR_DIMS(array));
  *elemsp = elems = palloc_array(Datum, nelems);
  if (nullsp)
    *nullsp = nulls = palloc0_array(bool, nelems);
  else
    nulls = NULL;
  *nelemsp = nelems;

  p = ARR_DATA_PTR(array);
  bitmap = ARR_NULLBITMAP(array);
  bitmask = 1;

  for (i = 0; i < nelems; i++)
  {
    /* Get source element, checking for NULL */
    if (bitmap && (*bitmap & bitmask) == 0)
    {
      elems[i] = (Datum) 0;
      if (nulls)
        nulls[i] = true;
      else
        ereport(ERROR,
            (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
             errmsg("null array element not allowed in this context")));
    }
    else
    {
      elems[i] = fetch_att(p, elmbyval, elmlen);
      p = att_addlength_pointer(p, elmlen, p);
      p = (char *) att_nominal_alignby(p, elmalignby);
    }

    /* advance bitmap pointer if any */
    if (bitmap)
    {
      bitmask <<= 1;
      if (bitmask == 0x100)
      {
        bitmap++;
        bitmask = 1;
      }
    }
  }
}

/*
 * Like deconstruct_array(), where elmtype must be a built-in type, and
 * elmlen/elmbyval/elmalign is looked up from hardcoded data.  This is often
 * useful when manipulating arrays from/for system catalogs.
 */
void
deconstruct_array_builtin(const ArrayType *array,
              Oid elmtype,
              Datum **elemsp, bool **nullsp, int *nelemsp)
{
  int     elmlen;
  bool    elmbyval;
  char    elmalign;

  switch (elmtype)
  {
    case CHAROID:
      elmlen = 1;
      elmbyval = true;
      elmalign = TYPALIGN_CHAR;
      break;

    case CSTRINGOID:
      elmlen = -2;
      elmbyval = false;
      elmalign = TYPALIGN_CHAR;
      break;

    case FLOAT8OID:
      elmlen = sizeof(float8);
      elmbyval = true;
      elmalign = TYPALIGN_DOUBLE;
      break;

    case INT2OID:
      elmlen = sizeof(int16);
      elmbyval = true;
      elmalign = TYPALIGN_SHORT;
      break;

    case INT4OID:
      elmlen = sizeof(int32);
      elmbyval = true;
      elmalign = TYPALIGN_INT;
      break;

    case OIDOID:
      elmlen = sizeof(Oid);
      elmbyval = true;
      elmalign = TYPALIGN_INT;
      break;

    case TEXTOID:
      elmlen = -1;
      elmbyval = false;
      elmalign = TYPALIGN_INT;
      break;

    case TIDOID:
      elmlen = sizeof(ItemPointerData);
      elmbyval = false;
      elmalign = TYPALIGN_SHORT;
      break;

    default:
      elog(ERROR, "type %u not supported by deconstruct_array_builtin()", elmtype);
      /* keep compiler quiet */
      elmlen = 0;
      elmbyval = false;
      elmalign = 0;
  }

  deconstruct_array(array, elmtype, elmlen, elmbyval, elmalign, elemsp, nullsp, nelemsp);
}

/*
 * array_contains_nulls --- detect whether an array has any null elements
 *
 * This gives an accurate answer, whereas testing ARR_HASNULL only tells
 * if the array *might* contain a null.
 */
bool
array_contains_nulls(const ArrayType *array)
{
  int     nelems;
  uint8    *bitmap;
  int     bitmask;

  /* Easy answer if there's no null bitmap */
  if (!ARR_HASNULL(array))
    return false;

  nelems = ArrayGetNItems(ARR_NDIM(array), ARR_DIMS(array));

  bitmap = ARR_NULLBITMAP(array);

  /* check whole bytes of the bitmap byte-at-a-time */
  while (nelems >= 8)
  {
    if (*bitmap != 0xFF)
      return true;
    bitmap++;
    nelems -= 8;
  }

  /* check last partial byte */
  bitmask = 1;
  while (nelems > 0)
  {
    if ((*bitmap & bitmask) == 0)
      return true;
    bitmask <<= 1;
    nelems--;
  }

  return false;
}


/*
 * array_eq :
 *      compares two arrays for equality
 * result :
 *      returns true if the arrays are equal, false otherwise.
 *
 * Note: we do not use array_cmp here, since equality may be meaningful in
 * datatypes that don't have a total ordering (and hence no btree support).
 */
Datum
array_eq(PG_FUNCTION_ARGS)
{
  LOCAL_FCINFO(locfcinfo, 2);
  AnyArrayType *array1 = PG_GETARG_ANY_ARRAY_P(0);
  AnyArrayType *array2 = PG_GETARG_ANY_ARRAY_P(1);
  Oid     collation = PG_GET_COLLATION();
  int     ndims1 = AARR_NDIM(array1);
  int     ndims2 = AARR_NDIM(array2);
  int      *dims1 = AARR_DIMS(array1);
  int      *dims2 = AARR_DIMS(array2);
  int      *lbs1 = AARR_LBOUND(array1);
  int      *lbs2 = AARR_LBOUND(array2);
  Oid     element_type = AARR_ELEMTYPE(array1);
  bool    result = true;
  int     nitems;
  TypeCacheEntry *typentry;
  int     typlen;
  bool    typbyval;
  char    typalign;
  array_iter  it1;
  array_iter  it2;
  int     i;

  if (element_type != AARR_ELEMTYPE(array2))
    ereport(ERROR,
        (errcode(ERRCODE_DATATYPE_MISMATCH),
         errmsg("cannot compare arrays of different element types")));

  /* fast path if the arrays do not have the same dimensionality */
  if (ndims1 != ndims2 ||
    memcmp(dims1, dims2, ndims1 * sizeof(int)) != 0 ||
    memcmp(lbs1, lbs2, ndims1 * sizeof(int)) != 0)
    result = false;
  else
  {
    /*
     * We arrange to look up the equality function only once per series of
     * calls, assuming the element type doesn't change underneath us.  The
     * typcache is used so that we have no memory leakage when being used
     * as an index support function.
     */
    typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
    if (typentry == NULL ||
      typentry->type_id != element_type)
    {
      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))));
      fcinfo->flinfo->fn_extra = typentry;
    }
    typlen = typentry->typlen;
    typbyval = typentry->typbyval;
    typalign = typentry->typalign;

    /*
     * apply the operator to each pair of array elements.
     */
    InitFunctionCallInfoData(*locfcinfo, &typentry->eq_opr_finfo, 2,
                 collation, NULL, NULL);

    /* Loop over source data */
    nitems = ArrayGetNItems(ndims1, dims1);
    array_iter_setup(&it1, array1, typlen, typbyval, typalign);
    array_iter_setup(&it2, array2, typlen, typbyval, typalign);

    for (i = 0; i < nitems; i++)
    {
      Datum   elt1;
      Datum   elt2;
      bool    isnull1;
      bool    isnull2;
      bool    oprresult;

      /* Get elements, checking for NULL */
      elt1 = array_iter_next(&it1, &isnull1, i);
      elt2 = array_iter_next(&it2, &isnull2, i);

      /*
       * We consider two NULLs equal; NULL and not-NULL are unequal.
       */
      if (isnull1 && isnull2)
        continue;
      if (isnull1 || isnull2)
      {
        result = false;
        break;
      }

      /*
       * Apply the operator to the element pair; treat NULL as false
       */
      locfcinfo->args[0].value = elt1;
      locfcinfo->args[0].isnull = false;
      locfcinfo->args[1].value = elt2;
      locfcinfo->args[1].isnull = false;
      locfcinfo->isnull = false;
      oprresult = DatumGetBool(FunctionCallInvoke(locfcinfo));
      if (locfcinfo->isnull || !oprresult)
      {
        result = false;
        break;
      }
    }
  }

  /* Avoid leaking memory when handed toasted input. */
  AARR_FREE_IF_COPY(array1, 0);
  AARR_FREE_IF_COPY(array2, 1);

  PG_RETURN_BOOL(result);
}


/*-----------------------------------------------------------------------------
 * array-array bool operators:
 *    Given two arrays, iterate comparison operators
 *    over the array. Uses logic similar to text comparison
 *    functions, except element-by-element instead of
 *    character-by-character.
 *----------------------------------------------------------------------------
 */

Datum
array_ne(PG_FUNCTION_ARGS)
{
  PG_RETURN_BOOL(!DatumGetBool(array_eq(fcinfo)));
}

Datum
array_lt(PG_FUNCTION_ARGS)
{
  PG_RETURN_BOOL(array_cmp(fcinfo) < 0);
}

Datum
array_gt(PG_FUNCTION_ARGS)
{
  PG_RETURN_BOOL(array_cmp(fcinfo) > 0);
}

Datum
array_le(PG_FUNCTION_ARGS)
{
  PG_RETURN_BOOL(array_cmp(fcinfo) <= 0);
}

Datum
array_ge(PG_FUNCTION_ARGS)
{
  PG_RETURN_BOOL(array_cmp(fcinfo) >= 0);
}

Datum
btarraycmp(PG_FUNCTION_ARGS)
{
  PG_RETURN_INT32(array_cmp(fcinfo));
}

/*
 * array_cmp()
 * Internal comparison function for arrays.
 *
 * Returns -1, 0 or 1
 */
static int
array_cmp(FunctionCallInfo fcinfo)
{
  LOCAL_FCINFO(locfcinfo, 2);
  AnyArrayType *array1 = PG_GETARG_ANY_ARRAY_P(0);
  AnyArrayType *array2 = PG_GETARG_ANY_ARRAY_P(1);
  Oid     collation = PG_GET_COLLATION();
  int     ndims1 = AARR_NDIM(array1);
  int     ndims2 = AARR_NDIM(array2);
  int      *dims1 = AARR_DIMS(array1);
  int      *dims2 = AARR_DIMS(array2);
  int     nitems1 = ArrayGetNItems(ndims1, dims1);
  int     nitems2 = ArrayGetNItems(ndims2, dims2);
  Oid     element_type = AARR_ELEMTYPE(array1);
  int     result = 0;
  TypeCacheEntry *typentry;
  int     typlen;
  bool    typbyval;
  char    typalign;
  int     min_nitems;
  array_iter  it1;
  array_iter  it2;
  int     i;

  if (element_type != AARR_ELEMTYPE(array2))
    ereport(ERROR,
        (errcode(ERRCODE_DATATYPE_MISMATCH),
         errmsg("cannot compare arrays of different element types")));

  /*
   * We arrange to look up the comparison function only once per series of
   * calls, assuming the element type doesn't change underneath us. The
   * typcache is used so that we have no memory leakage when being used as
   * an index support function.
   */
  typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
  if (typentry == NULL ||
    typentry->type_id != element_type)
  {
    typentry = lookup_type_cache(element_type,
                   TYPECACHE_CMP_PROC_FINFO);
    if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
      ereport(ERROR,
          (errcode(ERRCODE_UNDEFINED_FUNCTION),
           errmsg("could not identify a comparison function for type %s",
              format_type_be(element_type))));
    fcinfo->flinfo->fn_extra = typentry;
  }
  typlen = typentry->typlen;
  typbyval = typentry->typbyval;
  typalign = typentry->typalign;

  /*
   * apply the operator to each pair of array elements.
   */
  InitFunctionCallInfoData(*locfcinfo, &typentry->cmp_proc_finfo, 2,
               collation, NULL, NULL);

  /* Loop over source data */
  min_nitems = Min(nitems1, nitems2);
  array_iter_setup(&it1, array1, typlen, typbyval, typalign);
  array_iter_setup(&it2, array2, typlen, typbyval, typalign);

  for (i = 0; i < min_nitems; i++)
  {
    Datum   elt1;
    Datum   elt2;
    bool    isnull1;
    bool    isnull2;
    int32   cmpresult;

    /* Get elements, checking for NULL */
    elt1 = array_iter_next(&it1, &isnull1, i);
    elt2 = array_iter_next(&it2, &isnull2, i);

    /*
     * We consider two NULLs equal; NULL > not-NULL.
     */
    if (isnull1 && isnull2)
      continue;
    if (isnull1)
    {
      /* arg1 is greater than arg2 */
      result = 1;
      break;
    }
    if (isnull2)
    {
      /* arg1 is less than arg2 */
      result = -1;
      break;
    }

    /* Compare the pair of elements */
    locfcinfo->args[0].value = elt1;
    locfcinfo->args[0].isnull = false;
    locfcinfo->args[1].value = elt2;
    locfcinfo->args[1].isnull = false;
    cmpresult = DatumGetInt32(FunctionCallInvoke(locfcinfo));

    /* We don't expect comparison support functions to return null */
    Assert(!locfcinfo->isnull);

    if (cmpresult == 0)
      continue;     /* equal */

    if (cmpresult < 0)
    {
      /* arg1 is less than arg2 */
      result = -1;
      break;
    }
    else
    {
      /* arg1 is greater than arg2 */
      result = 1;
      break;
    }
  }

  /*
   * If arrays contain same data (up to end of shorter one), apply
   * additional rules to sort by dimensionality.  The relative significance
   * of the different bits of information is historical; mainly we just care
   * that we don't say "equal" for arrays of different dimensionality.
   */
  if (result == 0)
  {
    if (nitems1 != nitems2)
      result = (nitems1 < nitems2) ? -1 : 1;
    else if (ndims1 != ndims2)
      result = (ndims1 < ndims2) ? -1 : 1;
    else
    {
      for (i = 0; i < ndims1; i++)
      {
        if (dims1[i] != dims2[i])
        {
          result = (dims1[i] < dims2[i]) ? -1 : 1;
          break;
        }
      }
      if (result == 0)
      {
        int      *lbound1 = AARR_LBOUND(array1);
        int      *lbound2 = AARR_LBOUND(array2);

        for (i = 0; i < ndims1; i++)
        {
          if (lbound1[i] != lbound2[i])
          {
            result = (lbound1[i] < lbound2[i]) ? -1 : 1;
            break;
          }
        }
      }
    }
  }

  /* Avoid leaking memory when handed toasted input. */
  AARR_FREE_IF_COPY(array1, 0);
  AARR_FREE_IF_COPY(array2, 1);

  return result;
}


/*-----------------------------------------------------------------------------
 * array hashing
 *    Hash the elements and combine the results.
 *----------------------------------------------------------------------------
 */

Datum
hash_array(PG_FUNCTION_ARGS)
{
  LOCAL_FCINFO(locfcinfo, 1);
  AnyArrayType *array = PG_GETARG_ANY_ARRAY_P(0);
  int     ndims = AARR_NDIM(array);
  int      *dims = AARR_DIMS(array);
  Oid     element_type = AARR_ELEMTYPE(array);
  uint32    result = 1;
  int     nitems;
  TypeCacheEntry *typentry;
  int     typlen;
  bool    typbyval;
  char    typalign;
  int     i;
  array_iter  iter;

  /*
   * We arrange to look up the hash function only once per series of calls,
   * assuming the element type doesn't change underneath us.  The typcache
   * is used so that we have no memory leakage when being used as an index
   * support function.
   */
  typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
  if (typentry == NULL ||
    typentry->type_id != element_type)
  {
    typentry = lookup_type_cache(element_type,
                   TYPECACHE_HASH_PROC_FINFO);
    if (!OidIsValid(typentry->hash_proc_finfo.fn_oid) && element_type != RECORDOID)
      ereport(ERROR,
          (errcode(ERRCODE_UNDEFINED_FUNCTION),
           errmsg("could not identify a hash function for type %s",
              format_type_be(element_type))));

    /*
     * The type cache doesn't believe that record is hashable (see
     * cache_record_field_properties()), but since we're here, we're
     * committed to hashing, so we can assume it does.  Worst case, if any
     * components of the record don't support hashing, we will fail at
     * execution.
     */
    if (element_type == RECORDOID)
    {
      MemoryContext oldcontext;
      TypeCacheEntry *record_typentry;

      oldcontext = MemoryContextSwitchTo(fcinfo->flinfo->fn_mcxt);

      /*
       * Make fake type cache entry structure.  Note that we can't just
       * modify typentry, since that points directly into the type
       * cache.
       */
      record_typentry = palloc0_object(TypeCacheEntry);
      record_typentry->type_id = element_type;

      /* fill in what we need below */
      record_typentry->typlen = typentry->typlen;
      record_typentry->typbyval = typentry->typbyval;
      record_typentry->typalign = typentry->typalign;
      fmgr_info(F_HASH_RECORD, &record_typentry->hash_proc_finfo);

      MemoryContextSwitchTo(oldcontext);

      typentry = record_typentry;
    }

    fcinfo->flinfo->fn_extra = typentry;
  }

  typlen = typentry->typlen;
  typbyval = typentry->typbyval;
  typalign = typentry->typalign;

  /*
   * apply the hash function to each array element.
   */
  InitFunctionCallInfoData(*locfcinfo, &typentry->hash_proc_finfo, 1,
               PG_GET_COLLATION(), NULL, NULL);

  /* Loop over source data */
  nitems = ArrayGetNItems(ndims, dims);
  array_iter_setup(&iter, array, typlen, typbyval, typalign);

  for (i = 0; i < nitems; i++)
  {
    Datum   elt;
    bool    isnull;
    uint32    elthash;

    /* Get element, checking for NULL */
    elt = array_iter_next(&iter, &isnull, i);

    if (isnull)
    {
      /* Treat nulls as having hashvalue 0 */
      elthash = 0;
    }
    else
    {
      /* Apply the hash function */
      locfcinfo->args[0].value = elt;
      locfcinfo->args[0].isnull = false;
      elthash = DatumGetUInt32(FunctionCallInvoke(locfcinfo));
      /* We don't expect hash functions to return null */
      Assert(!locfcinfo->isnull);
    }

    /*
     * Combine hash values of successive elements by multiplying the
     * current value by 31 and adding on the new element's hash value.
     *
     * The result is a sum in which each element's hash value is
     * multiplied by a different power of 31. This is modulo 2^32
     * arithmetic, and the powers of 31 modulo 2^32 form a cyclic group of
     * order 2^27. So for arrays of up to 2^27 elements, each element's
     * hash value is multiplied by a different (odd) number, resulting in
     * a good mixing of all the elements' hash values.
     */
    result = (result << 5) - result + elthash;
  }

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

  PG_RETURN_UINT32(result);
}

/*
 * Returns 64-bit value by hashing a value to a 64-bit value, with a seed.
 * Otherwise, similar to hash_array.
 */
Datum
hash_array_extended(PG_FUNCTION_ARGS)
{
  LOCAL_FCINFO(locfcinfo, 2);
  AnyArrayType *array = PG_GETARG_ANY_ARRAY_P(0);
  uint64    seed = PG_GETARG_INT64(1);
  int     ndims = AARR_NDIM(array);
  int      *dims = AARR_DIMS(array);
  Oid     element_type = AARR_ELEMTYPE(array);
  uint64    result = 1;
  int     nitems;
  TypeCacheEntry *typentry;
  int     typlen;
  bool    typbyval;
  char    typalign;
  int     i;
  array_iter  iter;

  typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
  if (typentry == NULL ||
    typentry->type_id != element_type)
  {
    typentry = lookup_type_cache(element_type,
                   TYPECACHE_HASH_EXTENDED_PROC_FINFO);
    if (!OidIsValid(typentry->hash_extended_proc_finfo.fn_oid))
      ereport(ERROR,
          (errcode(ERRCODE_UNDEFINED_FUNCTION),
           errmsg("could not identify an extended hash function for type %s",
              format_type_be(element_type))));
    fcinfo->flinfo->fn_extra = typentry;
  }
  typlen = typentry->typlen;
  typbyval = typentry->typbyval;
  typalign = typentry->typalign;

  InitFunctionCallInfoData(*locfcinfo, &typentry->hash_extended_proc_finfo, 2,
               PG_GET_COLLATION(), NULL, NULL);

  /* Loop over source data */
  nitems = ArrayGetNItems(ndims, dims);
  array_iter_setup(&iter, array, typlen, typbyval, typalign);

  for (i = 0; i < nitems; i++)
  {
    Datum   elt;
    bool    isnull;
    uint64    elthash;

    /* Get element, checking for NULL */
    elt = array_iter_next(&iter, &isnull, i);

    if (isnull)
    {
      elthash = 0;
    }
    else
    {
      /* Apply the hash function */
      locfcinfo->args[0].value = elt;
      locfcinfo->args[0].isnull = false;
      locfcinfo->args[1].value = Int64GetDatum(seed);
      locfcinfo->args[1].isnull = false;
      elthash = DatumGetUInt64(FunctionCallInvoke(locfcinfo));
      /* We don't expect hash functions to return null */
      Assert(!locfcinfo->isnull);
    }

    result = (result << 5) - result + elthash;
  }

  AARR_FREE_IF_COPY(array, 0);

  PG_RETURN_UINT64(result);
}


/*-----------------------------------------------------------------------------
 * array overlap/containment comparisons
 *    These use the same methods of comparing array elements as array_eq.
 *    We consider only the elements of the arrays, ignoring dimensionality.
 *----------------------------------------------------------------------------
 */

/*
 * array_contain_compare :
 *      compares two arrays for overlap/containment
 *
 * When matchall is true, return true if all members of array1 are in array2.
 * When matchall is false, return true if any members of array1 are in array2.
 */
static bool
array_contain_compare(AnyArrayType *array1, AnyArrayType *array2, Oid collation,
            bool matchall, void **fn_extra)
{
  LOCAL_FCINFO(locfcinfo, 2);
  bool    result = matchall;
  Oid     element_type = AARR_ELEMTYPE(array1);
  TypeCacheEntry *typentry;
  int     nelems1;
  Datum    *values2;
  bool     *nulls2;
  int     nelems2;
  int     typlen;
  bool    typbyval;
  char    typalign;
  int     i;
  int     j;
  array_iter  it1;

  if (element_type != AARR_ELEMTYPE(array2))
    ereport(ERROR,
        (errcode(ERRCODE_DATATYPE_MISMATCH),
         errmsg("cannot compare arrays of different element types")));

  /*
   * We arrange to look up the equality function only once per series of
   * calls, assuming the element type doesn't change underneath us.  The
   * typcache is used so that we have no memory leakage when being used as
   * an index support function.
   */
  typentry = (TypeCacheEntry *) *fn_extra;
  if (typentry == NULL ||
    typentry->type_id != element_type)
  {
    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))));
    *fn_extra = typentry;
  }
  typlen = typentry->typlen;
  typbyval = typentry->typbyval;
  typalign = typentry->typalign;

  /*
   * Since we probably will need to scan array2 multiple times, it's
   * worthwhile to use deconstruct_array on it.  We scan array1 the hard way
   * however, since we very likely won't need to look at all of it.
   */
  if (VARATT_IS_EXPANDED_HEADER(array2))
  {
    /* This should be safe even if input is read-only */
    deconstruct_expanded_array(&(array2->xpn));
    values2 = array2->xpn.dvalues;
    nulls2 = array2->xpn.dnulls;
    nelems2 = array2->xpn.nelems;
  }
  else
    deconstruct_array((ArrayType *) array2,
              element_type, typlen, typbyval, typalign,
              &values2, &nulls2, &nelems2);

  /*
   * Apply the comparison operator to each pair of array elements.
   */
  InitFunctionCallInfoData(*locfcinfo, &typentry->eq_opr_finfo, 2,
               collation, NULL, NULL);

  /* Loop over source data */
  nelems1 = ArrayGetNItems(AARR_NDIM(array1), AARR_DIMS(array1));
  array_iter_setup(&it1, array1, typlen, typbyval, typalign);

  for (i = 0; i < nelems1; i++)
  {
    Datum   elt1;
    bool    isnull1;

    /* Get element, checking for NULL */
    elt1 = array_iter_next(&it1, &isnull1, i);

    /*
     * We assume that the comparison operator is strict, so a NULL can't
     * match anything.  XXX this diverges from the "NULL=NULL" behavior of
     * array_eq, should we act like that?
     */
    if (isnull1)
    {
      if (matchall)
      {
        result = false;
        break;
      }
      continue;
    }

    for (j = 0; j < nelems2; j++)
    {
      Datum   elt2 = values2[j];
      bool    isnull2 = nulls2 ? nulls2[j] : false;
      bool    oprresult;

      if (isnull2)
        continue;   /* can't match */

      /*
       * Apply the operator to the element pair; treat NULL as false
       */
      locfcinfo->args[0].value = elt1;
      locfcinfo->args[0].isnull = false;
      locfcinfo->args[1].value = elt2;
      locfcinfo->args[1].isnull = false;
      locfcinfo->isnull = false;
      oprresult = DatumGetBool(FunctionCallInvoke(locfcinfo));
      if (!locfcinfo->isnull && oprresult)
        break;
    }

    if (j < nelems2)
    {
      /* found a match for elt1 */
      if (!matchall)
      {
        result = true;
        break;
      }
    }
    else
    {
      /* no match for elt1 */
      if (matchall)
      {
        result = false;
        break;
      }
    }
  }

  return result;
}

Datum
arrayoverlap(PG_FUNCTION_ARGS)
{
  AnyArrayType *array1 = PG_GETARG_ANY_ARRAY_P(0);
  AnyArrayType *array2 = PG_GETARG_ANY_ARRAY_P(1);
  Oid     collation = PG_GET_COLLATION();
  bool    result;

  result = array_contain_compare(array1, array2, collation, false,
                   &fcinfo->flinfo->fn_extra);

  /* Avoid leaking memory when handed toasted input. */
  AARR_FREE_IF_COPY(array1, 0);
  AARR_FREE_IF_COPY(array2, 1);

  PG_RETURN_BOOL(result);
}

Datum
arraycontains(PG_FUNCTION_ARGS)
{
  AnyArrayType *array1 = PG_GETARG_ANY_ARRAY_P(0);
  AnyArrayType *array2 = PG_GETARG_ANY_ARRAY_P(1);
  Oid     collation = PG_GET_COLLATION();
  bool    result;

  result = array_contain_compare(array2, array1, collation, true,
                   &fcinfo->flinfo->fn_extra);

  /* Avoid leaking memory when handed toasted input. */
  AARR_FREE_IF_COPY(array1, 0);
  AARR_FREE_IF_COPY(array2, 1);

  PG_RETURN_BOOL(result);
}

Datum
arraycontained(PG_FUNCTION_ARGS)
{
  AnyArrayType *array1 = PG_GETARG_ANY_ARRAY_P(0);
  AnyArrayType *array2 = PG_GETARG_ANY_ARRAY_P(1);
  Oid     collation = PG_GET_COLLATION();
  bool    result;

  result = array_contain_compare(array1, array2, collation, true,
                   &fcinfo->flinfo->fn_extra);

  /* Avoid leaking memory when handed toasted input. */
  AARR_FREE_IF_COPY(array1, 0);
  AARR_FREE_IF_COPY(array2, 1);

  PG_RETURN_BOOL(result);
}


/*-----------------------------------------------------------------------------
 * Array iteration functions
 *    These functions are used to iterate efficiently through arrays
 *-----------------------------------------------------------------------------
 */

/*
 * array_create_iterator --- set up to iterate through an array
 *
 * If slice_ndim is zero, we will iterate element-by-element; the returned
 * datums are of the array's element type.
 *
 * If slice_ndim is 1..ARR_NDIM(arr), we will iterate by slices: the
 * returned datums are of the same array type as 'arr', but of size
 * equal to the rightmost N dimensions of 'arr'.
 *
 * The passed-in array must remain valid for the lifetime of the iterator.
 */
ArrayIterator
array_create_iterator(ArrayType *arr, int slice_ndim, ArrayMetaState *mstate)
{
  ArrayIterator iterator = palloc0_object(ArrayIteratorData);

  /*
   * Sanity-check inputs --- caller should have got this right already
   */
  Assert(arr);
  if (slice_ndim < 0 || slice_ndim > ARR_NDIM(arr))
    elog(ERROR, "invalid arguments to array_create_iterator");

  /*
   * Remember basic info about the array and its element type
   */
  iterator->arr = arr;
  iterator->nullbitmap = ARR_NULLBITMAP(arr);
  iterator->nitems = ArrayGetNItems(ARR_NDIM(arr), ARR_DIMS(arr));

  if (mstate != NULL)
  {
    Assert(mstate->element_type == ARR_ELEMTYPE(arr));

    iterator->typlen = mstate->typlen;
    iterator->typbyval = mstate->typbyval;
    iterator->typalign = mstate->typalign;
  }
  else
    get_typlenbyvalalign(ARR_ELEMTYPE(arr),
               &iterator->typlen,
               &iterator->typbyval,
               &iterator->typalign);
  iterator->typalignby = typalign_to_alignby(iterator->typalign);

  /*
   * Remember the slicing parameters.
   */
  iterator->slice_ndim = slice_ndim;

  if (slice_ndim > 0)
  {
    /*
     * Get pointers into the array's dims and lbound arrays to represent
     * the dims/lbound arrays of a slice.  These are the same as the
     * rightmost N dimensions of the array.
     */
    iterator->slice_dims = ARR_DIMS(arr) + ARR_NDIM(arr) - slice_ndim;
    iterator->slice_lbound = ARR_LBOUND(arr) + ARR_NDIM(arr) - slice_ndim;

    /*
     * Compute number of elements in a slice.
     */
    iterator->slice_len = ArrayGetNItems(slice_ndim,
                       iterator->slice_dims);

    /*
     * Create workspace for building sub-arrays.
     */
    iterator->slice_values = (Datum *)
      palloc(iterator->slice_len * sizeof(Datum));
    iterator->slice_nulls = (bool *)
      palloc(iterator->slice_len * sizeof(bool));
  }

  /*
   * Initialize our data pointer and linear element number.  These will
   * advance through the array during array_iterate().
   */
  iterator->data_ptr = ARR_DATA_PTR(arr);
  iterator->current_item = 0;

  return iterator;
}

/*
 * Iterate through the array referenced by 'iterator'.
 *
 * As long as there is another element (or slice), return it into
 * *value / *isnull, and return true.  Return false when no more data.
 */
bool
array_iterate(ArrayIterator iterator, Datum *value, bool *isnull)
{
  /* Done if we have reached the end of the array */
  if (iterator->current_item >= iterator->nitems)
    return false;

  if (iterator->slice_ndim == 0)
  {
    /*
     * Scalar case: return one element.
     */
    if (array_get_isnull(iterator->nullbitmap, iterator->current_item++))
    {
      *isnull = true;
      *value = (Datum) 0;
    }
    else
    {
      /* non-NULL, so fetch the individual Datum to return */
      char     *p = iterator->data_ptr;

      *isnull = false;
      *value = fetch_att(p, iterator->typbyval, iterator->typlen);

      /* Move our data pointer forward to the next element */
      p = att_addlength_pointer(p, iterator->typlen, p);
      p = (char *) att_nominal_alignby(p, iterator->typalignby);
      iterator->data_ptr = p;
    }
  }
  else
  {
    /*
     * Slice case: build and return an array of the requested size.
     */
    ArrayType  *result;
    Datum    *values = iterator->slice_values;
    bool     *nulls = iterator->slice_nulls;
    char     *p = iterator->data_ptr;
    int     i;

    for (i = 0; i < iterator->slice_len; i++)
    {
      if (array_get_isnull(iterator->nullbitmap,
                 iterator->current_item++))
      {
        nulls[i] = true;
        values[i] = (Datum) 0;
      }
      else
      {
        nulls[i] = false;
        values[i] = fetch_att(p, iterator->typbyval, iterator->typlen);

        /* Move our data pointer forward to the next element */
        p = att_addlength_pointer(p, iterator->typlen, p);
        p = (char *) att_nominal_alignby(p, iterator->typalignby);
      }
    }

    iterator->data_ptr = p;

    result = construct_md_array(values,
                  nulls,
                  iterator->slice_ndim,
                  iterator->slice_dims,
                  iterator->slice_lbound,
                  ARR_ELEMTYPE(iterator->arr),
                  iterator->typlen,
                  iterator->typbyval,
                  iterator->typalign);

    *isnull = false;
    *value = PointerGetDatum(result);
  }

  return true;
}

/*
 * Release an ArrayIterator data structure
 */
void
array_free_iterator(ArrayIterator iterator)
{
  if (iterator->slice_ndim > 0)
  {
    pfree(iterator->slice_values);
    pfree(iterator->slice_nulls);
  }
  pfree(iterator);
}


/***************************************************************************/
/******************|      Support  Routines       |*****************/
/***************************************************************************/

/*
 * Check whether a specific array element is NULL
 *
 * nullbitmap: pointer to array's null bitmap (NULL if none)
 * offset: 0-based linear element number of array element
 */
static bool
array_get_isnull(const uint8 *nullbitmap, int offset)
{
  if (nullbitmap == NULL)
    return false;     /* assume not null */
  if (nullbitmap[offset / 8] & (1 << (offset % 8)))
    return false;     /* not null */
  return true;
}

/*
 * Set a specific array element's null-bitmap entry
 *
 * nullbitmap: pointer to array's null bitmap (mustn't be NULL)
 * offset: 0-based linear element number of array element
 * isNull: null status to set
 */
static void
array_set_isnull(uint8 *nullbitmap, int offset, bool isNull)
{
  int     bitmask;

  nullbitmap += offset / 8;
  bitmask = 1 << (offset % 8);
  if (isNull)
    *nullbitmap &= ~bitmask;
  else
    *nullbitmap |= bitmask;
}

/*
 * Fetch array element at pointer, converted correctly to a Datum
 *
 * Caller must have handled case of NULL element
 */
static Datum
ArrayCast(char *value, bool byval, int len)
{
  return fetch_att(value, byval, len);
}

/*
 * Copy datum to *dest and return total space used (including align padding)
 *
 * Caller must have handled case of NULL element
 */
static int
ArrayCastAndSet(Datum src,
        int typlen,
        bool typbyval,
        uint8 typalignby,
        char *dest)
{
  int     inc;

  if (typlen > 0)
  {
    if (typbyval)
      store_att_byval(dest, src, typlen);
    else
      memmove(dest, DatumGetPointer(src), typlen);
    inc = att_nominal_alignby(typlen, typalignby);
  }
  else
  {
    Assert(!typbyval);
    inc = att_addlength_datum(0, typlen, src);
    memmove(dest, DatumGetPointer(src), inc);
    inc = att_nominal_alignby(inc, typalignby);
  }

  return inc;
}

/*
 * Advance ptr over nitems array elements
 *
 * ptr: starting location in array
 * offset: 0-based linear element number of first element (the one at *ptr)
 * nullbitmap: start of array's null bitmap, or NULL if none
 * nitems: number of array elements to advance over (>= 0)
 * typlen, typbyval, typalign: storage parameters of array element datatype
 *
 * It is caller's responsibility to ensure that nitems is within range
 */
static char *
array_seek(char *ptr, int offset, uint8 *nullbitmap, int nitems,
       int typlen, bool typbyval, char typalign)
{
  uint8   typalignby = typalign_to_alignby(typalign);
  int     bitmask;
  int     i;

  /* easy if fixed-size elements and no NULLs */
  if (typlen > 0 && !nullbitmap)
    return ptr + nitems * ((Size) att_nominal_alignby(typlen, typalignby));

  /* seems worth having separate loops for NULL and no-NULLs cases */
  if (nullbitmap)
  {
    nullbitmap += offset / 8;
    bitmask = 1 << (offset % 8);

    for (i = 0; i < nitems; i++)
    {
      if (*nullbitmap & bitmask)
      {
        ptr = att_addlength_pointer(ptr, typlen, ptr);
        ptr = (char *) att_nominal_alignby(ptr, typalignby);
      }
      bitmask <<= 1;
      if (bitmask == 0x100)
      {
        nullbitmap++;
        bitmask = 1;
      }
    }
  }
  else
  {
    for (i = 0; i < nitems; i++)
    {
      ptr = att_addlength_pointer(ptr, typlen, ptr);
      ptr = (char *) att_nominal_alignby(ptr, typalignby);
    }
  }
  return ptr;
}

/*
 * Compute total size of the nitems array elements starting at *ptr
 *
 * Parameters same as for array_seek
 */
static int
array_nelems_size(char *ptr, int offset, uint8 *nullbitmap, int nitems,
          int typlen, bool typbyval, char typalign)
{
  return array_seek(ptr, offset, nullbitmap, nitems,
            typlen, typbyval, typalign) - ptr;
}

/*
 * Copy nitems array elements from srcptr to destptr
 *
 * destptr: starting destination location (must be enough room!)
 * nitems: number of array elements to copy (>= 0)
 * srcptr: starting location in source array
 * offset: 0-based linear element number of first element (the one at *srcptr)
 * nullbitmap: start of source array's null bitmap, or NULL if none
 * typlen, typbyval, typalign: storage parameters of array element datatype
 *
 * Returns number of bytes copied
 *
 * NB: this does not take care of setting up the destination's null bitmap!
 */
static int
array_copy(char *destptr, int nitems,
       char *srcptr, int offset, uint8 *nullbitmap,
       int typlen, bool typbyval, char typalign)
{
  int     numbytes;

  numbytes = array_nelems_size(srcptr, offset, nullbitmap, nitems,
                 typlen, typbyval, typalign);
  memcpy(destptr, srcptr, numbytes);
  return numbytes;
}

/*
 * Copy nitems null-bitmap bits from source to destination
 *
 * destbitmap: start of destination array's null bitmap (mustn't be NULL)
 * destoffset: 0-based linear element number of first dest element
 * srcbitmap: start of source array's null bitmap, or NULL if none
 * srcoffset: 0-based linear element number of first source element
 * nitems: number of bits to copy (>= 0)
 *
 * If srcbitmap is NULL then we assume the source is all-non-NULL and
 * fill 1's into the destination bitmap.  Note that only the specified
 * bits in the destination map are changed, not any before or after.
 *
 * Note: this could certainly be optimized using standard bitblt methods.
 * However, it's not clear that the typical Postgres array has enough elements
 * to make it worth worrying too much.  For the moment, KISS.
 */
void
array_bitmap_copy(uint8 *destbitmap, int destoffset,
          const uint8 *srcbitmap, int srcoffset,
          int nitems)
{
  int     destbitmask,
        destbitval,
        srcbitmask,
        srcbitval;

  Assert(destbitmap);
  if (nitems <= 0)
    return;         /* don't risk fetch off end of memory */
  destbitmap += destoffset / 8;
  destbitmask = 1 << (destoffset % 8);
  destbitval = *destbitmap;
  if (srcbitmap)
  {
    srcbitmap += srcoffset / 8;
    srcbitmask = 1 << (srcoffset % 8);
    srcbitval = *srcbitmap;
    while (nitems-- > 0)
    {
      if (srcbitval & srcbitmask)
        destbitval |= destbitmask;
      else
        destbitval &= ~destbitmask;
      destbitmask <<= 1;
      if (destbitmask == 0x100)
      {
        *destbitmap++ = destbitval;
        destbitmask = 1;
        if (nitems > 0)
          destbitval = *destbitmap;
      }
      srcbitmask <<= 1;
      if (srcbitmask == 0x100)
      {
        srcbitmap++;
        srcbitmask = 1;
        if (nitems > 0)
          srcbitval = *srcbitmap;
      }
    }
    if (destbitmask != 1)
      *destbitmap = destbitval;
  }
  else
  {
    while (nitems-- > 0)
    {
      destbitval |= destbitmask;
      destbitmask <<= 1;
      if (destbitmask == 0x100)
      {
        *destbitmap++ = destbitval;
        destbitmask = 1;
        if (nitems > 0)
          destbitval = *destbitmap;
      }
    }
    if (destbitmask != 1)
      *destbitmap = destbitval;
  }
}

/*
 * Compute space needed for a slice of an array
 *
 * We assume the caller has verified that the slice coordinates are valid.
 */
static int
array_slice_size(char *arraydataptr, uint8 *arraynullsptr,
         int ndim, int *dim, int *lb,
         int *st, int *endp,
         int typlen, bool typbyval, char typalign)
{
  int     src_offset,
        span[MAXDIM],
        prod[MAXDIM],
        dist[MAXDIM],
        indx[MAXDIM];
  char     *ptr;
  int     i,
        j,
        inc;
  int     count = 0;
  uint8   typalignby = typalign_to_alignby(typalign);

  mda_get_range(ndim, span, st, endp);

  /* Pretty easy for fixed element length without nulls ... */
  if (typlen > 0 && !arraynullsptr)
    return ArrayGetNItems(ndim, span) * att_nominal_alignby(typlen, typalignby);

  /* Else gotta do it the hard way */
  src_offset = ArrayGetOffset(ndim, dim, lb, st);
  ptr = array_seek(arraydataptr, 0, arraynullsptr, src_offset,
           typlen, typbyval, typalign);
  mda_get_prod(ndim, dim, prod);
  mda_get_offset_values(ndim, dist, prod, span);
  for (i = 0; i < ndim; i++)
    indx[i] = 0;
  j = ndim - 1;
  do
  {
    if (dist[j])
    {
      ptr = array_seek(ptr, src_offset, arraynullsptr, dist[j],
               typlen, typbyval, typalign);
      src_offset += dist[j];
    }
    if (!array_get_isnull(arraynullsptr, src_offset))
    {
      inc = att_addlength_pointer(0, typlen, ptr);
      inc = att_nominal_alignby(inc, typalignby);
      ptr += inc;
      count += inc;
    }
    src_offset++;
  } while ((j = mda_next_tuple(ndim, indx, span)) != -1);
  return count;
}

/*
 * Extract a slice of an array into consecutive elements in the destination
 * array.
 *
 * We assume the caller has verified that the slice coordinates are valid,
 * allocated enough storage for the result, and initialized the header
 * of the new array.
 */
static void
array_extract_slice(ArrayType *newarray,
          int ndim,
          int *dim,
          int *lb,
          char *arraydataptr,
          uint8 *arraynullsptr,
          int *st,
          int *endp,
          int typlen,
          bool typbyval,
          char typalign)
{
  char     *destdataptr = ARR_DATA_PTR(newarray);
  uint8    *destnullsptr = ARR_NULLBITMAP(newarray);
  char     *srcdataptr;
  int     src_offset,
        dest_offset,
        prod[MAXDIM],
        span[MAXDIM],
        dist[MAXDIM],
        indx[MAXDIM];
  int     i,
        j,
        inc;

  src_offset = ArrayGetOffset(ndim, dim, lb, st);
  srcdataptr = array_seek(arraydataptr, 0, arraynullsptr, src_offset,
              typlen, typbyval, typalign);
  mda_get_prod(ndim, dim, prod);
  mda_get_range(ndim, span, st, endp);
  mda_get_offset_values(ndim, dist, prod, span);
  for (i = 0; i < ndim; i++)
    indx[i] = 0;
  dest_offset = 0;
  j = ndim - 1;
  do
  {
    if (dist[j])
    {
      /* skip unwanted elements */
      srcdataptr = array_seek(srcdataptr, src_offset, arraynullsptr,
                  dist[j],
                  typlen, typbyval, typalign);
      src_offset += dist[j];
    }
    inc = array_copy(destdataptr, 1,
             srcdataptr, src_offset, arraynullsptr,
             typlen, typbyval, typalign);
    if (destnullsptr)
      array_bitmap_copy(destnullsptr, dest_offset,
                arraynullsptr, src_offset,
                1);
    destdataptr += inc;
    srcdataptr += inc;
    src_offset++;
    dest_offset++;
  } while ((j = mda_next_tuple(ndim, indx, span)) != -1);
}

/*
 * Insert a slice into an array.
 *
 * ndim/dim[]/lb[] are dimensions of the original array.  A new array with
 * those same dimensions is to be constructed.  destArray must already
 * have been allocated and its header initialized.
 *
 * st[]/endp[] identify the slice to be replaced.  Elements within the slice
 * volume are taken from consecutive elements of the srcArray; elements
 * outside it are copied from origArray.
 *
 * We assume the caller has verified that the slice coordinates are valid.
 */
static void
array_insert_slice(ArrayType *destArray,
           ArrayType *origArray,
           ArrayType *srcArray,
           int ndim,
           int *dim,
           int *lb,
           int *st,
           int *endp,
           int typlen,
           bool typbyval,
           char typalign)
{
  char     *destPtr = ARR_DATA_PTR(destArray);
  char     *origPtr = ARR_DATA_PTR(origArray);
  char     *srcPtr = ARR_DATA_PTR(srcArray);
  uint8    *destBitmap = ARR_NULLBITMAP(destArray);
  uint8    *origBitmap = ARR_NULLBITMAP(origArray);
  uint8    *srcBitmap = ARR_NULLBITMAP(srcArray);
  int     orignitems = ArrayGetNItems(ARR_NDIM(origArray),
                      ARR_DIMS(origArray));
  int     dest_offset,
        orig_offset,
        src_offset,
        prod[MAXDIM],
        span[MAXDIM],
        dist[MAXDIM],
        indx[MAXDIM];
  int     i,
        j,
        inc;

  dest_offset = ArrayGetOffset(ndim, dim, lb, st);
  /* copy items before the slice start */
  inc = array_copy(destPtr, dest_offset,
           origPtr, 0, origBitmap,
           typlen, typbyval, typalign);
  destPtr += inc;
  origPtr += inc;
  if (destBitmap)
    array_bitmap_copy(destBitmap, 0, origBitmap, 0, dest_offset);
  orig_offset = dest_offset;
  mda_get_prod(ndim, dim, prod);
  mda_get_range(ndim, span, st, endp);
  mda_get_offset_values(ndim, dist, prod, span);
  for (i = 0; i < ndim; i++)
    indx[i] = 0;
  src_offset = 0;
  j = ndim - 1;
  do
  {
    /* Copy/advance over elements between here and next part of slice */
    if (dist[j])
    {
      inc = array_copy(destPtr, dist[j],
               origPtr, orig_offset, origBitmap,
               typlen, typbyval, typalign);
      destPtr += inc;
      origPtr += inc;
      if (destBitmap)
        array_bitmap_copy(destBitmap, dest_offset,
                  origBitmap, orig_offset,
                  dist[j]);
      dest_offset += dist[j];
      orig_offset += dist[j];
    }
    /* Copy new element at this slice position */
    inc = array_copy(destPtr, 1,
             srcPtr, src_offset, srcBitmap,
             typlen, typbyval, typalign);
    if (destBitmap)
      array_bitmap_copy(destBitmap, dest_offset,
                srcBitmap, src_offset,
                1);
    destPtr += inc;
    srcPtr += inc;
    dest_offset++;
    src_offset++;
    /* Advance over old element at this slice position */
    origPtr = array_seek(origPtr, orig_offset, origBitmap, 1,
               typlen, typbyval, typalign);
    orig_offset++;
  } while ((j = mda_next_tuple(ndim, indx, span)) != -1);

  /* don't miss any data at the end */
  array_copy(destPtr, orignitems - orig_offset,
         origPtr, orig_offset, origBitmap,
         typlen, typbyval, typalign);
  if (destBitmap)
    array_bitmap_copy(destBitmap, dest_offset,
              origBitmap, orig_offset,
              orignitems - orig_offset);
}

/*
 * initArrayResult - initialize an empty ArrayBuildState
 *
 *  element_type is the array element type (must be a valid array element type)
 *  rcontext is where to keep working state
 *  subcontext is a flag determining whether to use a separate memory context
 *
 * Note: there are two common schemes for using accumArrayResult().
 * In the older scheme, you start with a NULL ArrayBuildState pointer, and
 * call accumArrayResult once per element.  In this scheme you end up with
 * a NULL pointer if there were no elements, which you need to special-case.
 * In the newer scheme, call initArrayResult and then call accumArrayResult
 * once per element.  In this scheme you always end with a non-NULL pointer
 * that you can pass to makeArrayResult; you get an empty array if there
 * were no elements.  This is preferred if an empty array is what you want.
 *
 * It's possible to choose whether to create a separate memory context for the
 * array build state, or whether to allocate it directly within rcontext.
 *
 * When there are many concurrent small states (e.g. array_agg() using hash
 * aggregation of many small groups), using a separate memory context for each
 * one may result in severe memory bloat. In such cases, use the same memory
 * context to initialize all such array build states, and pass
 * subcontext=false.
 *
 * In cases when the array build states have different lifetimes, using a
 * single memory context is impractical. Instead, pass subcontext=true so that
 * the array build states can be freed individually.
 */
ArrayBuildState *
initArrayResult(Oid element_type, MemoryContext rcontext, bool subcontext)
{
  /*
   * When using a subcontext, we can afford to start with a somewhat larger
   * initial array size.  Without subcontexts, we'd better hope that most of
   * the states stay small ...
   */
  return initArrayResultWithSize(element_type, rcontext, subcontext,
                   subcontext ? 64 : 8);
}

/*
 * initArrayResultWithSize
 *    As initArrayResult, but allow the initial size of the allocated arrays
 *    to be specified.
 */
ArrayBuildState *
initArrayResultWithSize(Oid element_type, MemoryContext rcontext,
            bool subcontext, int initsize)
{
  ArrayBuildState *astate;
  MemoryContext arr_context = rcontext;

  /* Make a temporary context to hold all the junk */
  if (subcontext)
    arr_context = AllocSetContextCreate(rcontext,
                      "accumArrayResult",
                      ALLOCSET_DEFAULT_SIZES);

  astate = (ArrayBuildState *)
    MemoryContextAlloc(arr_context, sizeof(ArrayBuildState));
  astate->mcontext = arr_context;
  astate->private_cxt = subcontext;
  astate->alen = initsize;
  astate->dvalues = (Datum *)
    MemoryContextAlloc(arr_context, astate->alen * sizeof(Datum));
  astate->dnulls = (bool *)
    MemoryContextAlloc(arr_context, astate->alen * sizeof(bool));
  astate->nelems = 0;
  astate->element_type = element_type;
  get_typlenbyvalalign(element_type,
             &astate->typlen,
             &astate->typbyval,
             &astate->typalign);

  return astate;
}

/*
 * accumArrayResult - accumulate one (more) Datum for an array result
 *
 *  astate is working state (can be NULL on first call)
 *  dvalue/disnull represent the new Datum to append to the array
 *  element_type is the Datum's type (must be a valid array element type)
 *  rcontext is where to keep working state
 */
ArrayBuildState *
accumArrayResult(ArrayBuildState *astate,
         Datum dvalue, bool disnull,
         Oid element_type,
         MemoryContext rcontext)
{
  MemoryContext oldcontext;

  if (astate == NULL)
  {
    /* First time through --- initialize */
    astate = initArrayResult(element_type, rcontext, true);
  }
  else
  {
    Assert(astate->element_type == element_type);
  }

  oldcontext = MemoryContextSwitchTo(astate->mcontext);

  /* enlarge dvalues[]/dnulls[] if needed */
  if (astate->nelems >= astate->alen)
  {
    astate->alen *= 2;
    /* give an array-related error if we go past MaxAllocSize */
    if (!AllocSizeIsValid(astate->alen * sizeof(Datum)))
      ereport(ERROR,
          (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
           errmsg("array size exceeds the maximum allowed (%zu)",
              MaxAllocSize)));
    astate->dvalues = (Datum *)
      repalloc(astate->dvalues, astate->alen * sizeof(Datum));
    astate->dnulls = (bool *)
      repalloc(astate->dnulls, astate->alen * sizeof(bool));
  }

  /*
   * Ensure pass-by-ref stuff is copied into mcontext; and detoast it too if
   * it's varlena.  (You might think that detoasting is not needed here
   * because construct_md_array can detoast the array elements later.
   * However, we must not let construct_md_array modify the ArrayBuildState
   * because that would mean array_agg_finalfn damages its input, which is
   * verboten.  Also, this way frequently saves one copying step.)
   */
  if (!disnull && !astate->typbyval)
  {
    if (astate->typlen == -1)
      dvalue = PointerGetDatum(PG_DETOAST_DATUM_COPY(dvalue));
    else
      dvalue = datumCopy(dvalue, astate->typbyval, astate->typlen);
  }

  astate->dvalues[astate->nelems] = dvalue;
  astate->dnulls[astate->nelems] = disnull;
  astate->nelems++;

  MemoryContextSwitchTo(oldcontext);

  return astate;
}

/*
 * makeArrayResult - produce 1-D final result of accumArrayResult
 *
 * Note: only releases astate if it was initialized within a separate memory
 * context (i.e. using subcontext=true when calling initArrayResult).
 *
 *  astate is working state (must not be NULL)
 *  rcontext is where to construct result
 */
Datum
makeArrayResult(ArrayBuildState *astate,
        MemoryContext rcontext)
{
  int     ndims;
  int     dims[1];
  int     lbs[1];

  /* If no elements were presented, we want to create an empty array */
  ndims = (astate->nelems > 0) ? 1 : 0;
  dims[0] = astate->nelems;
  lbs[0] = 1;

  return makeMdArrayResult(astate, ndims, dims, lbs, rcontext,
               astate->private_cxt);
}

/*
 * makeMdArrayResult - produce multi-D final result of accumArrayResult
 *
 * beware: no check that specified dimensions match the number of values
 * accumulated.
 *
 * Note: if the astate was not initialized within a separate memory context
 * (that is, initArrayResult was called with subcontext=false), then using
 * release=true is illegal. Instead, release astate along with the rest of its
 * context when appropriate.
 *
 *  astate is working state (must not be NULL)
 *  rcontext is where to construct result
 *  release is true if okay to release working state
 */
Datum
makeMdArrayResult(ArrayBuildState *astate,
          int ndims,
          int *dims,
          int *lbs,
          MemoryContext rcontext,
          bool release)
{
  ArrayType  *result;
  MemoryContext oldcontext;

  /* Build the final array result in rcontext */
  oldcontext = MemoryContextSwitchTo(rcontext);

  result = construct_md_array(astate->dvalues,
                astate->dnulls,
                ndims,
                dims,
                lbs,
                astate->element_type,
                astate->typlen,
                astate->typbyval,
                astate->typalign);

  MemoryContextSwitchTo(oldcontext);

  /* Clean up all the junk */
  if (release)
  {
    Assert(astate->private_cxt);
    MemoryContextDelete(astate->mcontext);
  }

  return PointerGetDatum(result);
}

/*
 * The following three functions provide essentially the same API as
 * initArrayResult/accumArrayResult/makeArrayResult, but instead of accepting
 * inputs that are array elements, they accept inputs that are arrays and
 * produce an output array having N+1 dimensions.  The inputs must all have
 * identical dimensionality as well as element type.
 */

/*
 * initArrayResultArr - initialize an empty ArrayBuildStateArr
 *
 *  array_type is the array type (must be a valid varlena array type)
 *  element_type is the type of the array's elements (lookup if InvalidOid)
 *  rcontext is where to keep working state
 *  subcontext is a flag determining whether to use a separate memory context
 */
ArrayBuildStateArr *
initArrayResultArr(Oid array_type, Oid element_type, MemoryContext rcontext,
           bool subcontext)
{
  ArrayBuildStateArr *astate;
  MemoryContext arr_context = rcontext; /* by default use the parent ctx */

  /* Lookup element type, unless element_type already provided */
  if (!OidIsValid(element_type))
  {
    element_type = get_element_type(array_type);

    if (!OidIsValid(element_type))
      ereport(ERROR,
          (errcode(ERRCODE_DATATYPE_MISMATCH),
           errmsg("data type %s is not an array type",
              format_type_be(array_type))));
  }

  /* Make a temporary context to hold all the junk */
  if (subcontext)
    arr_context = AllocSetContextCreate(rcontext,
                      "accumArrayResultArr",
                      ALLOCSET_DEFAULT_SIZES);

  /* Note we initialize all fields to zero */
  astate = (ArrayBuildStateArr *)
    MemoryContextAllocZero(arr_context, sizeof(ArrayBuildStateArr));
  astate->mcontext = arr_context;
  astate->private_cxt = subcontext;

  /* Save relevant datatype information */
  astate->array_type = array_type;
  astate->element_type = element_type;

  return astate;
}

/*
 * accumArrayResultArr - accumulate one (more) sub-array for an array result
 *
 *  astate is working state (can be NULL on first call)
 *  dvalue/disnull represent the new sub-array to append to the array
 *  array_type is the array type (must be a valid varlena array type)
 *  rcontext is where to keep working state
 */
ArrayBuildStateArr *
accumArrayResultArr(ArrayBuildStateArr *astate,
          Datum dvalue, bool disnull,
          Oid array_type,
          MemoryContext rcontext)
{
  ArrayType  *arg;
  MemoryContext oldcontext;
  int      *dims,
         *lbs,
        ndims,
        nitems,
        ndatabytes;
  char     *data;
  int     i;
  int     newnitems;

  /*
   * We disallow accumulating null subarrays.  Another plausible definition
   * is to ignore them, but callers that want that can just skip calling
   * this function.
   */
  if (disnull)
    ereport(ERROR,
        (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
         errmsg("cannot accumulate null arrays")));

  /* Detoast input array in caller's context */
  arg = DatumGetArrayTypeP(dvalue);

  if (astate == NULL)
    astate = initArrayResultArr(array_type, InvalidOid, rcontext, true);
  else
    Assert(astate->array_type == array_type);

  oldcontext = MemoryContextSwitchTo(astate->mcontext);

  /* Collect this input's dimensions */
  ndims = ARR_NDIM(arg);
  dims = ARR_DIMS(arg);
  lbs = ARR_LBOUND(arg);
  data = ARR_DATA_PTR(arg);
  nitems = ArrayGetNItems(ndims, dims);
  ndatabytes = ARR_SIZE(arg) - ARR_DATA_OFFSET(arg);

  /* Check that the array doesn't grow too large */
  newnitems = astate->nitems + nitems;
  if (newnitems > MaxArraySize)
    ereport(ERROR,
        (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
         errmsg("array size exceeds the maximum allowed (%zu)",
            MaxArraySize)));

  if (astate->ndims == 0)
  {
    /* First input; check/save the dimensionality info */

    /* Should we allow empty inputs and just produce an empty output? */
    if (ndims == 0)
      ereport(ERROR,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("cannot accumulate empty arrays")));
    if (ndims + 1 > MAXDIM)
      ereport(ERROR,
          (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
           errmsg("number of array dimensions (%d) exceeds the maximum allowed (%d)",
              ndims + 1, MAXDIM)));

    /*
     * The output array will have n+1 dimensions, with the ones after the
     * first matching the input's dimensions.
     */
    astate->ndims = ndims + 1;
    astate->dims[0] = 0;
    memcpy(&astate->dims[1], dims, ndims * sizeof(int));
    astate->lbs[0] = 1;
    memcpy(&astate->lbs[1], lbs, ndims * sizeof(int));

    /* Allocate at least enough data space for this item */
    astate->abytes = pg_nextpower2_32(Max(1024, ndatabytes + 1));
    astate->data = (char *) palloc(astate->abytes);
  }
  else
  {
    /* Second or later input: must match first input's dimensionality */
    if (astate->ndims != ndims + 1)
      ereport(ERROR,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("cannot accumulate arrays of different dimensionality")));
    for (i = 0; i < ndims; i++)
    {
      if (astate->dims[i + 1] != dims[i] || astate->lbs[i + 1] != lbs[i])
        ereport(ERROR,
            (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
             errmsg("cannot accumulate arrays of different dimensionality")));
    }

    /* Enlarge data space if needed */
    if (astate->nbytes + ndatabytes > astate->abytes)
    {
      astate->abytes = Max(astate->abytes * 2,
                 astate->nbytes + ndatabytes);
      astate->data = (char *) repalloc(astate->data, astate->abytes);
    }
  }

  /*
   * Copy the data portion of the sub-array.  Note we assume that the
   * advertised data length of the sub-array is properly aligned.  We do not
   * have to worry about detoasting elements since whatever's in the
   * sub-array should be OK already.
   */
  memcpy(astate->data + astate->nbytes, data, ndatabytes);
  astate->nbytes += ndatabytes;

  /* Deal with null bitmap if needed */
  if (astate->nullbitmap || ARR_HASNULL(arg))
  {
    if (astate->nullbitmap == NULL)
    {
      /*
       * First input with nulls; we must retrospectively handle any
       * previous inputs by marking all their items non-null.
       */
      astate->aitems = pg_nextpower2_32(Max(256, newnitems + 1));
      astate->nullbitmap = (uint8 *) palloc((astate->aitems + 7) / 8);
      array_bitmap_copy(astate->nullbitmap, 0,
                NULL, 0,
                astate->nitems);
    }
    else if (newnitems > astate->aitems)
    {
      astate->aitems = Max(astate->aitems * 2, newnitems);
      astate->nullbitmap = (uint8 *)
        repalloc(astate->nullbitmap, (astate->aitems + 7) / 8);
    }
    array_bitmap_copy(astate->nullbitmap, astate->nitems,
              ARR_NULLBITMAP(arg), 0,
              nitems);
  }

  astate->nitems = newnitems;
  astate->dims[0] += 1;

  MemoryContextSwitchTo(oldcontext);

  /* Release detoasted copy if any */
  if (arg != DatumGetPointer(dvalue))
    pfree(arg);

  return astate;
}

/*
 * makeArrayResultArr - produce N+1-D final result of accumArrayResultArr
 *
 *  astate is working state (must not be NULL)
 *  rcontext is where to construct result
 *  release is true if okay to release working state
 */
Datum
makeArrayResultArr(ArrayBuildStateArr *astate,
           MemoryContext rcontext,
           bool release)
{
  ArrayType  *result;
  MemoryContext oldcontext;

  /* Build the final array result in rcontext */
  oldcontext = MemoryContextSwitchTo(rcontext);

  if (astate->ndims == 0)
  {
    /* No inputs, return empty array */
    result = construct_empty_array(astate->element_type);
  }
  else
  {
    int     dataoffset,
          nbytes;

    /* Check for overflow of the array dimensions */
    (void) ArrayGetNItems(astate->ndims, astate->dims);
    ArrayCheckBounds(astate->ndims, astate->dims, astate->lbs);

    /* Compute required space */
    nbytes = astate->nbytes;
    if (astate->nullbitmap != NULL)
    {
      dataoffset = ARR_OVERHEAD_WITHNULLS(astate->ndims, astate->nitems);
      nbytes += dataoffset;
    }
    else
    {
      dataoffset = 0;
      nbytes += ARR_OVERHEAD_NONULLS(astate->ndims);
    }

    result = (ArrayType *) palloc0(nbytes);
    SET_VARSIZE(result, nbytes);
    result->ndim = astate->ndims;
    result->dataoffset = dataoffset;
    result->elemtype = astate->element_type;

    memcpy(ARR_DIMS(result), astate->dims, astate->ndims * sizeof(int));
    memcpy(ARR_LBOUND(result), astate->lbs, astate->ndims * sizeof(int));
    memcpy(ARR_DATA_PTR(result), astate->data, astate->nbytes);

    if (astate->nullbitmap != NULL)
      array_bitmap_copy(ARR_NULLBITMAP(result), 0,
                astate->nullbitmap, 0,
                astate->nitems);
  }

  MemoryContextSwitchTo(oldcontext);

  /* Clean up all the junk */
  if (release)
  {
    Assert(astate->private_cxt);
    MemoryContextDelete(astate->mcontext);
  }

  return PointerGetDatum(result);
}

/*
 * The following three functions provide essentially the same API as
 * initArrayResult/accumArrayResult/makeArrayResult, but can accept either
 * scalar or array inputs, invoking the appropriate set of functions above.
 */

/*
 * initArrayResultAny - initialize an empty ArrayBuildStateAny
 *
 *  input_type is the input datatype (either element or array type)
 *  rcontext is where to keep working state
 *  subcontext is a flag determining whether to use a separate memory context
 */
ArrayBuildStateAny *
initArrayResultAny(Oid input_type, MemoryContext rcontext, bool subcontext)
{
  ArrayBuildStateAny *astate;

  /*
   * int2vector and oidvector will satisfy both get_element_type and
   * get_array_type.  We prefer to treat them as scalars, to be consistent
   * with get_promoted_array_type.  Hence, check get_array_type not
   * get_element_type.
   */
  if (!OidIsValid(get_array_type(input_type)))
  {
    /* Array case */
    ArrayBuildStateArr *arraystate;

    arraystate = initArrayResultArr(input_type, InvalidOid, rcontext, subcontext);
    astate = (ArrayBuildStateAny *)
      MemoryContextAlloc(arraystate->mcontext,
                 sizeof(ArrayBuildStateAny));
    astate->scalarstate = NULL;
    astate->arraystate = arraystate;
  }
  else
  {
    /* Scalar case */
    ArrayBuildState *scalarstate;

    scalarstate = initArrayResult(input_type, rcontext, subcontext);
    astate = (ArrayBuildStateAny *)
      MemoryContextAlloc(scalarstate->mcontext,
                 sizeof(ArrayBuildStateAny));
    astate->scalarstate = scalarstate;
    astate->arraystate = NULL;
  }

  return astate;
}

/*
 * accumArrayResultAny - accumulate one (more) input for an array result
 *
 *  astate is working state (can be NULL on first call)
 *  dvalue/disnull represent the new input to append to the array
 *  input_type is the input datatype (either element or array type)
 *  rcontext is where to keep working state
 */
ArrayBuildStateAny *
accumArrayResultAny(ArrayBuildStateAny *astate,
          Datum dvalue, bool disnull,
          Oid input_type,
          MemoryContext rcontext)
{
  if (astate == NULL)
    astate = initArrayResultAny(input_type, rcontext, true);

  if (astate->scalarstate)
    (void) accumArrayResult(astate->scalarstate,
                dvalue, disnull,
                input_type, rcontext);
  else
    (void) accumArrayResultArr(astate->arraystate,
                   dvalue, disnull,
                   input_type, rcontext);

  return astate;
}

/*
 * makeArrayResultAny - produce final result of accumArrayResultAny
 *
 *  astate is working state (must not be NULL)
 *  rcontext is where to construct result
 *  release is true if okay to release working state
 */
Datum
makeArrayResultAny(ArrayBuildStateAny *astate,
           MemoryContext rcontext, bool release)
{
  Datum   result;

  if (astate->scalarstate)
  {
    /* Must use makeMdArrayResult to support "release" parameter */
    int     ndims;
    int     dims[1];
    int     lbs[1];

    /* If no elements were presented, we want to create an empty array */
    ndims = (astate->scalarstate->nelems > 0) ? 1 : 0;
    dims[0] = astate->scalarstate->nelems;
    lbs[0] = 1;

    result = makeMdArrayResult(astate->scalarstate, ndims, dims, lbs,
                   rcontext, release);
  }
  else
  {
    result = makeArrayResultArr(astate->arraystate,
                  rcontext, release);
  }
  return result;
}


Datum
array_larger(PG_FUNCTION_ARGS)
{
  if (array_cmp(fcinfo) > 0)
    PG_RETURN_DATUM(PG_GETARG_DATUM(0));
  else
    PG_RETURN_DATUM(PG_GETARG_DATUM(1));
}

Datum
array_smaller(PG_FUNCTION_ARGS)
{
  if (array_cmp(fcinfo) < 0)
    PG_RETURN_DATUM(PG_GETARG_DATUM(0));
  else
    PG_RETURN_DATUM(PG_GETARG_DATUM(1));
}


typedef struct generate_subscripts_fctx
{
  int32   lower;
  int32   upper;
  bool    reverse;
} generate_subscripts_fctx;

/*
 * generate_subscripts(array anyarray, dim int [, reverse bool])
 *    Returns all subscripts of the array for any dimension
 */
Datum
generate_subscripts(PG_FUNCTION_ARGS)
{
  FuncCallContext *funcctx;
  MemoryContext oldcontext;
  generate_subscripts_fctx *fctx;

  /* stuff done only on the first call of the function */
  if (SRF_IS_FIRSTCALL())
  {
    AnyArrayType *v = PG_GETARG_ANY_ARRAY_P(0);
    int     reqdim = PG_GETARG_INT32(1);
    int      *lb,
           *dimv;

    /* create a function context for cross-call persistence */
    funcctx = SRF_FIRSTCALL_INIT();

    /* Sanity check: does it look like an array at all? */
    if (AARR_NDIM(v) <= 0 || AARR_NDIM(v) > MAXDIM)
      SRF_RETURN_DONE(funcctx);

    /* Sanity check: was the requested dim valid */
    if (reqdim <= 0 || reqdim > AARR_NDIM(v))
      SRF_RETURN_DONE(funcctx);

    /*
     * switch to memory context appropriate for multiple function calls
     */
    oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
    fctx = palloc_object(generate_subscripts_fctx);

    lb = AARR_LBOUND(v);
    dimv = AARR_DIMS(v);

    fctx->lower = lb[reqdim - 1];
    fctx->upper = dimv[reqdim - 1] + lb[reqdim - 1] - 1;
    fctx->reverse = (PG_NARGS() < 3) ? false : PG_GETARG_BOOL(2);

    funcctx->user_fctx = fctx;

    MemoryContextSwitchTo(oldcontext);
  }

  funcctx = SRF_PERCALL_SETUP();

  fctx = funcctx->user_fctx;

  if (fctx->lower <= fctx->upper)
  {
    if (!fctx->reverse)
      SRF_RETURN_NEXT(funcctx, Int32GetDatum(fctx->lower++));
    else
      SRF_RETURN_NEXT(funcctx, Int32GetDatum(fctx->upper--));
  }
  else
    /* done when there are no more elements left */
    SRF_RETURN_DONE(funcctx);
}

/*
 * generate_subscripts_nodir
 *    Implements the 2-argument version of generate_subscripts
 */
Datum
generate_subscripts_nodir(PG_FUNCTION_ARGS)
{
  /* just call the other one -- it can handle both cases */
  return generate_subscripts(fcinfo);
}

/*
 * array_fill_with_lower_bounds
 *    Create and fill array with defined lower bounds.
 */
Datum
array_fill_with_lower_bounds(PG_FUNCTION_ARGS)
{
  ArrayType  *dims;
  ArrayType  *lbs;
  ArrayType  *result;
  Oid     elmtype;
  Datum   value;
  bool    isnull;

  if (PG_ARGISNULL(1) || PG_ARGISNULL(2))
    ereport(ERROR,
        (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
         errmsg("dimension array or low bound array cannot be null")));

  dims = PG_GETARG_ARRAYTYPE_P(1);
  lbs = PG_GETARG_ARRAYTYPE_P(2);

  if (!PG_ARGISNULL(0))
  {
    value = PG_GETARG_DATUM(0);
    isnull = false;
  }
  else
  {
    value = 0;
    isnull = true;
  }

  elmtype = get_fn_expr_argtype(fcinfo->flinfo, 0);
  if (!OidIsValid(elmtype))
    elog(ERROR, "could not determine data type of input");

  result = array_fill_internal(dims, lbs, value, isnull, elmtype, fcinfo);
  PG_RETURN_ARRAYTYPE_P(result);
}

/*
 * array_fill
 *    Create and fill array with default lower bounds.
 */
Datum
array_fill(PG_FUNCTION_ARGS)
{
  ArrayType  *dims;
  ArrayType  *result;
  Oid     elmtype;
  Datum   value;
  bool    isnull;

  if (PG_ARGISNULL(1))
    ereport(ERROR,
        (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
         errmsg("dimension array or low bound array cannot be null")));

  dims = PG_GETARG_ARRAYTYPE_P(1);

  if (!PG_ARGISNULL(0))
  {
    value = PG_GETARG_DATUM(0);
    isnull = false;
  }
  else
  {
    value = 0;
    isnull = true;
  }

  elmtype = get_fn_expr_argtype(fcinfo->flinfo, 0);
  if (!OidIsValid(elmtype))
    elog(ERROR, "could not determine data type of input");

  result = array_fill_internal(dims, NULL, value, isnull, elmtype, fcinfo);
  PG_RETURN_ARRAYTYPE_P(result);
}

static ArrayType *
create_array_envelope(int ndims, int *dimv, int *lbsv, int nbytes,
            Oid elmtype, int dataoffset)
{
  ArrayType  *result;

  result = (ArrayType *) palloc0(nbytes);
  SET_VARSIZE(result, nbytes);
  result->ndim = ndims;
  result->dataoffset = dataoffset;
  result->elemtype = elmtype;
  memcpy(ARR_DIMS(result), dimv, ndims * sizeof(int));
  memcpy(ARR_LBOUND(result), lbsv, ndims * sizeof(int));

  return result;
}

static ArrayType *
array_fill_internal(ArrayType *dims, ArrayType *lbs,
          Datum value, bool isnull, Oid elmtype,
          FunctionCallInfo fcinfo)
{
  ArrayType  *result;
  int      *dimv;
  int      *lbsv;
  int     ndims;
  int     nitems;
  int     deflbs[MAXDIM];
  int16   elmlen;
  bool    elmbyval;
  char    elmalign;
  uint8   elmalignby;
  ArrayMetaState *my_extra;

  /*
   * Params checks
   */
  if (ARR_NDIM(dims) > 1)
    ereport(ERROR,
        (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
         errmsg("wrong number of array subscripts"),
         errdetail("Dimension array must be one dimensional.")));

  if (array_contains_nulls(dims))
    ereport(ERROR,
        (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
         errmsg("dimension values cannot be null")));

  dimv = (int *) ARR_DATA_PTR(dims);
  ndims = (ARR_NDIM(dims) > 0) ? ARR_DIMS(dims)[0] : 0;

  if (ndims < 0)       /* we do allow zero-dimension arrays */
    ereport(ERROR,
        (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
         errmsg("invalid number of dimensions: %d", ndims)));
  if (ndims > MAXDIM)
    ereport(ERROR,
        (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
         errmsg("number of array dimensions (%d) exceeds the maximum allowed (%d)",
            ndims, MAXDIM)));

  if (lbs != NULL)
  {
    if (ARR_NDIM(lbs) > 1)
      ereport(ERROR,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("wrong number of array subscripts"),
           errdetail("Dimension array must be one dimensional.")));

    if (array_contains_nulls(lbs))
      ereport(ERROR,
          (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
           errmsg("dimension values cannot be null")));

    if (ndims != ((ARR_NDIM(lbs) > 0) ? ARR_DIMS(lbs)[0] : 0))
      ereport(ERROR,
          (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
           errmsg("wrong number of array subscripts"),
           errdetail("Low bound array has different size than dimensions array.")));

    lbsv = (int *) ARR_DATA_PTR(lbs);
  }
  else
  {
    int     i;

    for (i = 0; i < MAXDIM; i++)
      deflbs[i] = 1;

    lbsv = deflbs;
  }

  /* This checks for overflow of the array dimensions */
  nitems = ArrayGetNItems(ndims, dimv);
  ArrayCheckBounds(ndims, dimv, lbsv);

  /* fast track for empty array */
  if (nitems <= 0)
    return construct_empty_array(elmtype);

  /*
   * We arrange to look up info about element type 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 = InvalidOid;
  }

  if (my_extra->element_type != elmtype)
  {
    /* Get info about element type */
    get_typlenbyvalalign(elmtype,
               &my_extra->typlen,
               &my_extra->typbyval,
               &my_extra->typalign);
    my_extra->element_type = elmtype;
  }

  elmlen = my_extra->typlen;
  elmbyval = my_extra->typbyval;
  elmalign = my_extra->typalign;
  elmalignby = typalign_to_alignby(elmalign);

  /* compute required space */
  if (!isnull)
  {
    int     i;
    char     *p;
    int     nbytes;
    int     totbytes;

    /* make sure data is not toasted */
    if (elmlen == -1)
      value = PointerGetDatum(PG_DETOAST_DATUM(value));

    nbytes = att_addlength_datum(0, elmlen, value);
    nbytes = att_nominal_alignby(nbytes, elmalignby);
    Assert(nbytes > 0);

    totbytes = nbytes * nitems;

    /* check for overflow of multiplication or total request */
    if (totbytes / nbytes != nitems ||
      !AllocSizeIsValid(totbytes))
      ereport(ERROR,
          (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
           errmsg("array size exceeds the maximum allowed (%zu)",
              MaxAllocSize)));

    /*
     * This addition can't overflow, but it might cause us to go past
     * MaxAllocSize.  We leave it to palloc to complain in that case.
     */
    totbytes += ARR_OVERHEAD_NONULLS(ndims);

    result = create_array_envelope(ndims, dimv, lbsv, totbytes,
                     elmtype, 0);

    p = ARR_DATA_PTR(result);
    for (i = 0; i < nitems; i++)
      p += ArrayCastAndSet(value, elmlen, elmbyval, elmalignby, p);
  }
  else
  {
    int     nbytes;
    int     dataoffset;

    dataoffset = ARR_OVERHEAD_WITHNULLS(ndims, nitems);
    nbytes = dataoffset;

    result = create_array_envelope(ndims, dimv, lbsv, nbytes,
                     elmtype, dataoffset);

    /* create_array_envelope already zeroed the bitmap, so we're done */
  }

  return result;
}


/*
 * UNNEST
 */
Datum
array_unnest(PG_FUNCTION_ARGS)
{
  typedef struct
  {
    array_iter  iter;
    int     nextelem;
    int     numelems;
  } array_unnest_fctx;

  FuncCallContext *funcctx;
  array_unnest_fctx *fctx;
  MemoryContext oldcontext;

  /* stuff done only on the first call of the function */
  if (SRF_IS_FIRSTCALL())
  {
    AnyArrayType *arr;
    int16   elmlen;
    bool    elmbyval;
    char    elmalign;

    /* create a function context for cross-call persistence */
    funcctx = SRF_FIRSTCALL_INIT();

    /*
     * switch to memory context appropriate for multiple function calls
     */
    oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);

    /*
     * Get the array value and detoast if needed.  We can't do this
     * earlier because if we have to detoast, we want the detoasted copy
     * to be in multi_call_memory_ctx, so it will go away when we're done
     * and not before.  (If no detoast happens, we assume the originally
     * passed array will stick around till then.)
     */
    arr = PG_GETARG_ANY_ARRAY_P(0);

    /* allocate memory for user context */
    fctx = palloc_object(array_unnest_fctx);

    /* get element-type data */
    if (VARATT_IS_EXPANDED_HEADER(arr))
    {
      /* we can just grab the type data from expanded array */
      elmlen = arr->xpn.typlen;
      elmbyval = arr->xpn.typbyval;
      elmalign = arr->xpn.typalign;
    }
    else
      get_typlenbyvalalign(AARR_ELEMTYPE(arr),
                 &elmlen,
                 &elmbyval,
                 &elmalign);

    /* initialize state */
    array_iter_setup(&fctx->iter, arr, elmlen, elmbyval, elmalign);
    fctx->nextelem = 0;
    fctx->numelems = ArrayGetNItems(AARR_NDIM(arr), AARR_DIMS(arr));

    funcctx->user_fctx = fctx;
    MemoryContextSwitchTo(oldcontext);
  }

  /* stuff done on every call of the function */
  funcctx = SRF_PERCALL_SETUP();
  fctx = funcctx->user_fctx;

  if (fctx->nextelem < fctx->numelems)
  {
    int     offset = fctx->nextelem++;
    Datum   elem;

    elem = array_iter_next(&fctx->iter, &fcinfo->isnull, offset);

    SRF_RETURN_NEXT(funcctx, elem);
  }
  else
  {
    /* do when there is no more left */
    SRF_RETURN_DONE(funcctx);
  }
}

/*
 * Planner support function for array_unnest(anyarray)
 *
 * Note: this is now also used for information_schema._pg_expandarray(),
 * which is simply a wrapper around array_unnest().
 */
Datum
array_unnest_support(PG_FUNCTION_ARGS)
{
  Node     *rawreq = (Node *) PG_GETARG_POINTER(0);
  Node     *ret = NULL;

  if (IsA(rawreq, SupportRequestRows))
  {
    /* Try to estimate the number of rows returned */
    SupportRequestRows *req = (SupportRequestRows *) rawreq;

    if (is_funcclause(req->node)) /* be paranoid */
    {
      List     *args = ((FuncExpr *) req->node)->args;
      Node     *arg1;

      /* We can use estimated argument values here */
      arg1 = estimate_expression_value(req->root, linitial(args));

      req->rows = estimate_array_length(req->root, arg1);
      ret = (Node *) req;
    }
  }

  PG_RETURN_POINTER(ret);
}


/*
 * array_replace/array_remove support
 *
 * Find all array entries matching (not distinct from) search/search_isnull,
 * and delete them if remove is true, else replace them with
 * replace/replace_isnull.  Comparisons are done using the specified
 * collation.  fcinfo is passed only for caching purposes.
 */
static ArrayType *
array_replace_internal(ArrayType *array,
             Datum search, bool search_isnull,
             Datum replace, bool replace_isnull,
             bool remove, Oid collation,
             FunctionCallInfo fcinfo)
{
  LOCAL_FCINFO(locfcinfo, 2);
  ArrayType  *result;
  Oid     element_type;
  Datum    *values;
  bool     *nulls;
  int      *dim;
  int     ndim;
  int     nitems,
        nresult;
  int     i;
  int32   nbytes = 0;
  int32   dataoffset;
  bool    hasnulls;
  int     typlen;
  bool    typbyval;
  char    typalign;
  uint8   typalignby;
  char     *arraydataptr;
  uint8    *bitmap;
  int     bitmask;
  bool    changed = false;
  TypeCacheEntry *typentry;

  element_type = ARR_ELEMTYPE(array);
  ndim = ARR_NDIM(array);
  dim = ARR_DIMS(array);
  nitems = ArrayGetNItems(ndim, dim);

  /* Return input array unmodified if it is empty */
  if (nitems <= 0)
    return array;

  /*
   * We can't remove elements from multi-dimensional arrays, since the
   * result might not be rectangular.
   */
  if (remove && ndim > 1)
    ereport(ERROR,
        (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
         errmsg("removing elements from multidimensional arrays is not supported")));

  /*
   * We arrange to look up the equality function only once per series of
   * calls, assuming the element type doesn't change underneath us.
   */
  typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
  if (typentry == NULL ||
    typentry->type_id != element_type)
  {
    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))));
    fcinfo->flinfo->fn_extra = typentry;
  }
  typlen = typentry->typlen;
  typbyval = typentry->typbyval;
  typalign = typentry->typalign;
  typalignby = typalign_to_alignby(typalign);

  /*
   * Detoast values if they are toasted.  The replacement value must be
   * detoasted for insertion into the result array, while detoasting the
   * search value only once saves cycles.
   */
  if (typlen == -1)
  {
    if (!search_isnull)
      search = PointerGetDatum(PG_DETOAST_DATUM(search));
    if (!replace_isnull)
      replace = PointerGetDatum(PG_DETOAST_DATUM(replace));
  }

  /* Prepare to apply the comparison operator */
  InitFunctionCallInfoData(*locfcinfo, &typentry->eq_opr_finfo, 2,
               collation, NULL, NULL);

  /* Allocate temporary arrays for new values */
  values = (Datum *) palloc(nitems * sizeof(Datum));
  nulls = (bool *) palloc(nitems * sizeof(bool));

  /* Loop over source data */
  arraydataptr = ARR_DATA_PTR(array);
  bitmap = ARR_NULLBITMAP(array);
  bitmask = 1;
  hasnulls = false;
  nresult = 0;

  for (i = 0; i < nitems; i++)
  {
    Datum   elt;
    bool    isNull;
    bool    oprresult;
    bool    skip = false;

    /* Get source element, checking for NULL */
    if (bitmap && (*bitmap & bitmask) == 0)
    {
      isNull = true;
      /* If searching for NULL, we have a match */
      if (search_isnull)
      {
        if (remove)
        {
          skip = true;
          changed = true;
        }
        else if (!replace_isnull)
        {
          values[nresult] = replace;
          isNull = false;
          changed = true;
        }
      }
    }
    else
    {
      isNull = false;
      elt = fetch_att(arraydataptr, typbyval, typlen);
      arraydataptr = att_addlength_datum(arraydataptr, typlen, elt);
      arraydataptr = (char *) att_nominal_alignby(arraydataptr, typalignby);

      if (search_isnull)
      {
        /* no match possible, keep element */
        values[nresult] = elt;
      }
      else
      {
        /*
         * Apply the operator to the element pair; treat NULL as false
         */
        locfcinfo->args[0].value = elt;
        locfcinfo->args[0].isnull = false;
        locfcinfo->args[1].value = search;
        locfcinfo->args[1].isnull = false;
        locfcinfo->isnull = false;
        oprresult = DatumGetBool(FunctionCallInvoke(locfcinfo));
        if (locfcinfo->isnull || !oprresult)
        {
          /* no match, keep element */
          values[nresult] = elt;
        }
        else
        {
          /* match, so replace or delete */
          changed = true;
          if (remove)
            skip = true;
          else
          {
            values[nresult] = replace;
            isNull = replace_isnull;
          }
        }
      }
    }

    if (!skip)
    {
      nulls[nresult] = isNull;
      if (isNull)
        hasnulls = true;
      else
      {
        /* Update total result size */
        nbytes = att_addlength_datum(nbytes, typlen, values[nresult]);
        nbytes = att_nominal_alignby(nbytes, typalignby);
        /* check for overflow of total request */
        if (!AllocSizeIsValid(nbytes))
          ereport(ERROR,
              (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
               errmsg("array size exceeds the maximum allowed (%zu)",
                  MaxAllocSize)));
      }
      nresult++;
    }

    /* advance bitmap pointer if any */
    if (bitmap)
    {
      bitmask <<= 1;
      if (bitmask == 0x100)
      {
        bitmap++;
        bitmask = 1;
      }
    }
  }

  /*
   * If not changed just return the original array
   */
  if (!changed)
  {
    pfree(values);
    pfree(nulls);
    return array;
  }

  /* If all elements were removed return an empty array */
  if (nresult == 0)
  {
    pfree(values);
    pfree(nulls);
    return construct_empty_array(element_type);
  }

  /* Allocate and initialize the result array */
  if (hasnulls)
  {
    dataoffset = ARR_OVERHEAD_WITHNULLS(ndim, nresult);
    nbytes += dataoffset;
  }
  else
  {
    dataoffset = 0;     /* marker for no null bitmap */
    nbytes += ARR_OVERHEAD_NONULLS(ndim);
  }
  result = (ArrayType *) palloc0(nbytes);
  SET_VARSIZE(result, nbytes);
  result->ndim = ndim;
  result->dataoffset = dataoffset;
  result->elemtype = element_type;
  memcpy(ARR_DIMS(result), ARR_DIMS(array), ndim * sizeof(int));
  memcpy(ARR_LBOUND(result), ARR_LBOUND(array), ndim * sizeof(int));

  if (remove)
  {
    /* Adjust the result length */
    ARR_DIMS(result)[0] = nresult;
  }

  /* Insert data into result array */
  CopyArrayEls(result,
         values, nulls, nresult,
         typlen, typbyval, typalign,
         false);

  pfree(values);
  pfree(nulls);

  return result;
}

/*
 * Remove any occurrences of an element from an array
 *
 * If used on a multi-dimensional array this will raise an error.
 */
Datum
array_remove(PG_FUNCTION_ARGS)
{
  ArrayType  *array;
  Datum   search = PG_GETARG_DATUM(1);
  bool    search_isnull = PG_ARGISNULL(1);

  if (PG_ARGISNULL(0))
    PG_RETURN_NULL();
  array = PG_GETARG_ARRAYTYPE_P(0);

  array = array_replace_internal(array,
                   search, search_isnull,
                   (Datum) 0, true,
                   true, PG_GET_COLLATION(),
                   fcinfo);
  PG_RETURN_ARRAYTYPE_P(array);
}

/*
 * Replace any occurrences of an element in an array
 */
Datum
array_replace(PG_FUNCTION_ARGS)
{
  ArrayType  *array;
  Datum   search = PG_GETARG_DATUM(1);
  bool    search_isnull = PG_ARGISNULL(1);
  Datum   replace = PG_GETARG_DATUM(2);
  bool    replace_isnull = PG_ARGISNULL(2);

  if (PG_ARGISNULL(0))
    PG_RETURN_NULL();
  array = PG_GETARG_ARRAYTYPE_P(0);

  array = array_replace_internal(array,
                   search, search_isnull,
                   replace, replace_isnull,
                   false, PG_GET_COLLATION(),
                   fcinfo);
  PG_RETURN_ARRAYTYPE_P(array);
}

/*
 * Implements width_bucket(anyelement, anyarray).
 *
 * 'thresholds' is an array containing lower bound values for each bucket;
 * these must be sorted from smallest to largest, or bogus results will be
 * produced.  If N thresholds are supplied, the output is from 0 to N:
 * 0 is for inputs < first threshold, N is for inputs >= last threshold.
 */
Datum
width_bucket_array(PG_FUNCTION_ARGS)
{
  Datum   operand = PG_GETARG_DATUM(0);
  ArrayType  *thresholds = PG_GETARG_ARRAYTYPE_P(1);
  Oid     collation = PG_GET_COLLATION();
  Oid     element_type = ARR_ELEMTYPE(thresholds);
  int     result;

  /* Check input */
  if (ARR_NDIM(thresholds) > 1)
    ereport(ERROR,
        (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
         errmsg("thresholds must be one-dimensional array")));

  if (array_contains_nulls(thresholds))
    ereport(ERROR,
        (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
         errmsg("thresholds array must not contain NULLs")));

  /* We have a dedicated implementation for float8 data */
  if (element_type == FLOAT8OID)
    result = width_bucket_array_float8(operand, thresholds);
  else
  {
    TypeCacheEntry *typentry;

    /* Cache information about the input type */
    typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
    if (typentry == NULL ||
      typentry->type_id != element_type)
    {
      typentry = lookup_type_cache(element_type,
                     TYPECACHE_CMP_PROC_FINFO);
      if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
        ereport(ERROR,
            (errcode(ERRCODE_UNDEFINED_FUNCTION),
             errmsg("could not identify a comparison function for type %s",
                format_type_be(element_type))));
      fcinfo->flinfo->fn_extra = typentry;
    }

    /*
     * We have separate implementation paths for fixed- and variable-width
     * types, since indexing the array is a lot cheaper in the first case.
     */
    if (typentry->typlen > 0)
      result = width_bucket_array_fixed(operand, thresholds,
                        collation, typentry);
    else
      result = width_bucket_array_variable(operand, thresholds,
                         collation, typentry);
  }

  /* Avoid leaking memory when handed toasted input. */
  PG_FREE_IF_COPY(thresholds, 1);

  PG_RETURN_INT32(result);
}

/*
 * width_bucket_array for float8 data.
 */
static int
width_bucket_array_float8(Datum operand, ArrayType *thresholds)
{
  float8    op = DatumGetFloat8(operand);
  float8     *thresholds_data;
  int     left;
  int     right;

  /*
   * Since we know the array contains no NULLs, we can just index it
   * directly.
   */
  thresholds_data = (float8 *) ARR_DATA_PTR(thresholds);

  left = 0;
  right = ArrayGetNItems(ARR_NDIM(thresholds), ARR_DIMS(thresholds));

  /*
   * If the probe value is a NaN, it's greater than or equal to all possible
   * threshold values (including other NaNs), so we need not search.  Note
   * that this would give the same result as searching even if the array
   * contains multiple NaNs (as long as they're correctly sorted), since the
   * loop logic will find the rightmost of multiple equal threshold values.
   */
  if (isnan(op))
    return right;

  /* Find the bucket */
  while (left < right)
  {
    int     mid = (left + right) / 2;

    if (isnan(thresholds_data[mid]) || op < thresholds_data[mid])
      right = mid;
    else
      left = mid + 1;
  }

  return left;
}

/*
 * width_bucket_array for generic fixed-width data types.
 */
static int
width_bucket_array_fixed(Datum operand,
             ArrayType *thresholds,
             Oid collation,
             TypeCacheEntry *typentry)
{
  LOCAL_FCINFO(locfcinfo, 2);
  char     *thresholds_data;
  int     typlen = typentry->typlen;
  bool    typbyval = typentry->typbyval;
  int     left;
  int     right;

  /*
   * Since we know the array contains no NULLs, we can just index it
   * directly.
   */
  thresholds_data = (char *) ARR_DATA_PTR(thresholds);

  InitFunctionCallInfoData(*locfcinfo, &typentry->cmp_proc_finfo, 2,
               collation, NULL, NULL);

  /* Find the bucket */
  left = 0;
  right = ArrayGetNItems(ARR_NDIM(thresholds), ARR_DIMS(thresholds));
  while (left < right)
  {
    int     mid = (left + right) / 2;
    char     *ptr;
    int32   cmpresult;

    ptr = thresholds_data + mid * typlen;

    locfcinfo->args[0].value = operand;
    locfcinfo->args[0].isnull = false;
    locfcinfo->args[1].value = fetch_att(ptr, typbyval, typlen);
    locfcinfo->args[1].isnull = false;

    cmpresult = DatumGetInt32(FunctionCallInvoke(locfcinfo));

    /* We don't expect comparison support functions to return null */
    Assert(!locfcinfo->isnull);

    if (cmpresult < 0)
      right = mid;
    else
      left = mid + 1;
  }

  return left;
}

/*
 * width_bucket_array for generic variable-width data types.
 */
static int
width_bucket_array_variable(Datum operand,
              ArrayType *thresholds,
              Oid collation,
              TypeCacheEntry *typentry)
{
  LOCAL_FCINFO(locfcinfo, 2);
  char     *thresholds_data;
  int     typlen = typentry->typlen;
  bool    typbyval = typentry->typbyval;
  char    typalign = typentry->typalign;
  uint8   typalignby = typalign_to_alignby(typalign);
  int     left;
  int     right;

  thresholds_data = (char *) ARR_DATA_PTR(thresholds);

  InitFunctionCallInfoData(*locfcinfo, &typentry->cmp_proc_finfo, 2,
               collation, NULL, NULL);

  /* Find the bucket */
  left = 0;
  right = ArrayGetNItems(ARR_NDIM(thresholds), ARR_DIMS(thresholds));
  while (left < right)
  {
    int     mid = (left + right) / 2;
    char     *ptr;
    int     i;
    int32   cmpresult;

    /* Locate mid'th array element by advancing from left element */
    ptr = thresholds_data;
    for (i = left; i < mid; i++)
    {
      ptr = att_addlength_pointer(ptr, typlen, ptr);
      ptr = (char *) att_nominal_alignby(ptr, typalignby);
    }

    locfcinfo->args[0].value = operand;
    locfcinfo->args[0].isnull = false;
    locfcinfo->args[1].value = fetch_att(ptr, typbyval, typlen);
    locfcinfo->args[1].isnull = false;

    cmpresult = DatumGetInt32(FunctionCallInvoke(locfcinfo));

    /* We don't expect comparison support functions to return null */
    Assert(!locfcinfo->isnull);

    if (cmpresult < 0)
      right = mid;
    else
    {
      left = mid + 1;

      /*
       * Move the thresholds pointer to match new "left" index, so we
       * don't have to seek over those elements again.  This trick
       * ensures we do only O(N) array indexing work, not O(N^2).
       */
      ptr = att_addlength_pointer(ptr, typlen, ptr);
      thresholds_data = (char *) att_nominal_alignby(ptr, typalignby);
    }
  }

  return left;
}

/*
 * Trim the last N elements from an array by building an appropriate slice.
 * Only the first dimension is trimmed.
 */
Datum
trim_array(PG_FUNCTION_ARGS)
{
  ArrayType  *v = PG_GETARG_ARRAYTYPE_P(0);
  int     n = PG_GETARG_INT32(1);
  int     array_length = (ARR_NDIM(v) > 0) ? ARR_DIMS(v)[0] : 0;
  int16   elmlen;
  bool    elmbyval;
  char    elmalign;
  int     lower[MAXDIM];
  int     upper[MAXDIM];
  bool    lowerProvided[MAXDIM];
  bool    upperProvided[MAXDIM];
  Datum   result;

  /* Per spec, throw an error if out of bounds */
  if (n < 0 || n > array_length)
    ereport(ERROR,
        (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
         errmsg("number of elements to trim must be between 0 and %d",
            array_length)));

  /* Set all the bounds as unprovided except the first upper bound */
  memset(lowerProvided, false, sizeof(lowerProvided));
  memset(upperProvided, false, sizeof(upperProvided));
  if (ARR_NDIM(v) > 0)
  {
    upper[0] = ARR_LBOUND(v)[0] + array_length - n - 1;
    upperProvided[0] = true;
  }

  /* Fetch the needed information about the element type */
  get_typlenbyvalalign(ARR_ELEMTYPE(v), &elmlen, &elmbyval, &elmalign);

  /* Get the slice */
  result = array_get_slice(PointerGetDatum(v), 1,
               upper, lower, upperProvided, lowerProvided,
               -1, elmlen, elmbyval, elmalign);

  PG_RETURN_DATUM(result);
}

Coverage Report

Created: 2026-08-13 07:12