src/backend/utils/adt/arrayutils.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * arrayutils.c
   4  *        This file contains some support routines required for array functions.
   5  *
   6  * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/utils/adt/arrayutils.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "catalog/pg_type.h"
  19 #include "common/int.h"
  20 #include "utils/array.h"
  21 #include "utils/builtins.h"
  22 #include "utils/memutils.h"
  23
  24
  25 /*
  26  * Convert subscript list into linear element number (from 0)
  27  *
  28  * We assume caller has already range-checked the dimensions and subscripts,
  29  * so no overflow is possible.
  30  */
  31 int
  32 ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
  33 {
  34         int                     i,
  35                                 scale = 1,
  36                                 offset = 0;
  37
  38         for (i = n - 1; i >= 0; i--)
  39         {
  40                 offset += (indx[i] - lb[i]) * scale;
  41                 scale *= dim[i];
  42         }
  43         return offset;
  44 }
  45
  46 /*
  47  * Convert array dimensions into number of elements
  48  *
  49  * This must do overflow checking, since it is used to validate that a user
  50  * dimensionality request doesn't overflow what we can handle.
  51  *
  52  * The multiplication overflow check only works on machines that have int64
  53  * arithmetic, but that is nearly all platforms these days, and doing check
  54  * divides for those that don't seems way too expensive.
  55  */
  56 int
  57 ArrayGetNItems(int ndim, const int *dims)
  58 {
  59         return ArrayGetNItemsSafe(ndim, dims, NULL);
  60 }
  61
  62 /*
  63  * This entry point can return the error into an ErrorSaveContext
  64  * instead of throwing an exception.  -1 is returned after an error.
  65  */
  66 int
  67 ArrayGetNItemsSafe(int ndim, const int *dims, struct Node *escontext)
  68 {
  69         int32           ret;
  70         int                     i;
  71
  72         if (ndim <= 0)
  73                 return 0;
  74         ret = 1;
  75         for (i = 0; i < ndim; i++)
  76         {
  77                 int64           prod;
  78
  79                 /* A negative dimension implies that UB-LB overflowed ... */
  80                 if (dims[i] < 0)
  81                         ereturn(escontext, -1,
  82                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
  83                                          errmsg("array size exceeds the maximum allowed (%d)",
  84                                                         (int) MaxArraySize)));
  85
  86                 prod = (int64) ret * (int64) dims[i];
  87
  88                 ret = (int32) prod;
  89                 if ((int64) ret != prod)
  90                         ereturn(escontext, -1,
  91                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
  92                                          errmsg("array size exceeds the maximum allowed (%d)",
  93                                                         (int) MaxArraySize)));
  94         }
  95         Assert(ret >= 0);
  96         if ((Size) ret > MaxArraySize)
  97                 ereturn(escontext, -1,
  98                                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
  99                                  errmsg("array size exceeds the maximum allowed (%d)",
 100                                                 (int) MaxArraySize)));
 101         return (int) ret;
 102 }
 103
 104 /*
 105  * Verify sanity of proposed lower-bound values for an array
 106  *
 107  * The lower-bound values must not be so large as to cause overflow when
 108  * calculating subscripts, e.g. lower bound 2147483640 with length 10
 109  * must be disallowed.  We actually insist that dims[i] + lb[i] be
 110  * computable without overflow, meaning that an array with last subscript
 111  * equal to INT_MAX will be disallowed.
 112  *
 113  * It is assumed that the caller already called ArrayGetNItems, so that
 114  * overflowed (negative) dims[] values have been eliminated.
 115  */
 116 void
 117 ArrayCheckBounds(int ndim, const int *dims, const int *lb)
 118 {
 119         (void) ArrayCheckBoundsSafe(ndim, dims, lb, NULL);
 120 }
 121
 122 /*
 123  * This entry point can return the error into an ErrorSaveContext
 124  * instead of throwing an exception.
 125  */
 126 bool
 127 ArrayCheckBoundsSafe(int ndim, const int *dims, const int *lb,
 128                                          struct Node *escontext)
 129 {
 130         int                     i;
 131
 132         for (i = 0; i < ndim; i++)
 133         {
 134                 /* PG_USED_FOR_ASSERTS_ONLY prevents variable-isn't-read warnings */
 135                 int32           sum PG_USED_FOR_ASSERTS_ONLY;
 136
 137                 if (pg_add_s32_overflow(dims[i], lb[i], &sum))
 138                         ereturn(escontext, false,
 139                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 140                                          errmsg("array lower bound is too large: %d",
 141                                                         lb[i])));
 142         }
 143
 144         return true;
 145 }
 146
 147 /*
 148  * Compute ranges (sub-array dimensions) for an array slice
 149  *
 150  * We assume caller has validated slice endpoints, so overflow is impossible
 151  */
 152 void
 153 mda_get_range(int n, int *span, const int *st, const int *endp)
 154 {
 155         int                     i;
 156
 157         for (i = 0; i < n; i++)
 158                 span[i] = endp[i] - st[i] + 1;
 159 }
 160
 161 /*
 162  * Compute products of array dimensions, ie, scale factors for subscripts
 163  *
 164  * We assume caller has validated dimensions, so overflow is impossible
 165  */
 166 void
 167 mda_get_prod(int n, const int *range, int *prod)
 168 {
 169         int                     i;
 170
 171         prod[n - 1] = 1;
 172         for (i = n - 2; i >= 0; i--)
 173                 prod[i] = prod[i + 1] * range[i + 1];
 174 }
 175
 176 /*
 177  * From products of whole-array dimensions and spans of a sub-array,
 178  * compute offset distances needed to step through subarray within array
 179  *
 180  * We assume caller has validated dimensions, so overflow is impossible
 181  */
 182 void
 183 mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
 184 {
 185         int                     i,
 186                                 j;
 187
 188         dist[n - 1] = 0;
 189         for (j = n - 2; j >= 0; j--)
 190         {
 191                 dist[j] = prod[j] - 1;
 192                 for (i = j + 1; i < n; i++)
 193                         dist[j] -= (span[i] - 1) * prod[i];
 194         }
 195 }
 196
 197 /*
 198  * Generates the tuple that is lexicographically one greater than the current
 199  * n-tuple in "curr", with the restriction that the i-th element of "curr" is
 200  * less than the i-th element of "span".
 201  *
 202  * Returns -1 if no next tuple exists, else the subscript position (0..n-1)
 203  * corresponding to the dimension to advance along.
 204  *
 205  * We assume caller has validated dimensions, so overflow is impossible
 206  */
 207 int
 208 mda_next_tuple(int n, int *curr, const int *span)
 209 {
 210         int                     i;
 211
 212         if (n <= 0)
 213                 return -1;
 214
 215         curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
 216         for (i = n - 1; i && curr[i] == 0; i--)
 217                 curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
 218
 219         if (i)
 220                 return i;
 221         if (curr[0])
 222                 return 0;
 223
 224         return -1;
 225 }
 226
 227 /*
 228  * ArrayGetIntegerTypmods: verify that argument is a 1-D cstring array,
 229  * and get the contents converted to integers.  Returns a palloc'd array
 230  * and places the length at *n.
 231  */
 232 int32 *
 233 ArrayGetIntegerTypmods(ArrayType *arr, int *n)
 234 {
 235         int32      *result;
 236         Datum      *elem_values;
 237         int                     i;
 238
 239         if (ARR_ELEMTYPE(arr) != CSTRINGOID)
 240                 ereport(ERROR,
 241                                 (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
 242                                  errmsg("typmod array must be type cstring[]")));
 243
 244         if (ARR_NDIM(arr) != 1)
 245                 ereport(ERROR,
 246                                 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
 247                                  errmsg("typmod array must be one-dimensional")));
 248
 249         if (array_contains_nulls(arr))
 250                 ereport(ERROR,
 251                                 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 252                                  errmsg("typmod array must not contain nulls")));
 253
 254         deconstruct_array_builtin(arr, CSTRINGOID, &elem_values, NULL, n);
 255
 256         result = (int32 *) palloc(*n * sizeof(int32));
 257
 258         for (i = 0; i < *n; i++)
 259                 result[i] = pg_strtoint32(DatumGetCString(elem_values[i]));
 260
 261         pfree(elem_values);
 262
 263         return result;
 264 }