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-2022, 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  * Same, but subscripts are assumed 0-based, and use a scale array
  48  * instead of raw dimension data (see mda_get_prod to create scale array)
  49  */
  50 int
  51 ArrayGetOffset0(int n, const int *tup, const int *scale)
  52 {
  53         int                     i,
  54                                 lin = 0;
  55
  56         for (i = 0; i < n; i++)
  57                 lin += tup[i] * scale[i];
  58         return lin;
  59 }
  60
  61 /*
  62  * Convert array dimensions into number of elements
  63  *
  64  * This must do overflow checking, since it is used to validate that a user
  65  * dimensionality request doesn't overflow what we can handle.
  66  *
  67  * We limit array sizes to at most about a quarter billion elements,
  68  * so that it's not necessary to check for overflow in quite so many
  69  * places --- for instance when palloc'ing Datum arrays.
  70  *
  71  * The multiplication overflow check only works on machines that have int64
  72  * arithmetic, but that is nearly all platforms these days, and doing check
  73  * divides for those that don't seems way too expensive.
  74  */
  75 int
  76 ArrayGetNItems(int ndim, const int *dims)
  77 {
  78         int32           ret;
  79         int                     i;
  80
  81 #define MaxArraySize ((Size) (MaxAllocSize / sizeof(Datum)))
  82
  83         if (ndim <= 0)
  84                 return 0;
  85         ret = 1;
  86         for (i = 0; i < ndim; i++)
  87         {
  88                 int64           prod;
  89
  90                 /* A negative dimension implies that UB-LB overflowed ... */
  91                 if (dims[i] < 0)
  92                         ereport(ERROR,
  93                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
  94                                          errmsg("array size exceeds the maximum allowed (%d)",
  95                                                         (int) MaxArraySize)));
  96
  97                 prod = (int64) ret * (int64) dims[i];
  98
  99                 ret = (int32) prod;
 100                 if ((int64) ret != prod)
 101                         ereport(ERROR,
 102                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 103                                          errmsg("array size exceeds the maximum allowed (%d)",
 104                                                         (int) MaxArraySize)));
 105         }
 106         Assert(ret >= 0);
 107         if ((Size) ret > MaxArraySize)
 108                 ereport(ERROR,
 109                                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 110                                  errmsg("array size exceeds the maximum allowed (%d)",
 111                                                 (int) MaxArraySize)));
 112         return (int) ret;
 113 }
 114
 115 /*
 116  * Verify sanity of proposed lower-bound values for an array
 117  *
 118  * The lower-bound values must not be so large as to cause overflow when
 119  * calculating subscripts, e.g. lower bound 2147483640 with length 10
 120  * must be disallowed.  We actually insist that dims[i] + lb[i] be
 121  * computable without overflow, meaning that an array with last subscript
 122  * equal to INT_MAX will be disallowed.
 123  *
 124  * It is assumed that the caller already called ArrayGetNItems, so that
 125  * overflowed (negative) dims[] values have been eliminated.
 126  */
 127 void
 128 ArrayCheckBounds(int ndim, const int *dims, const int *lb)
 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                         ereport(ERROR,
 139                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 140                                          errmsg("array lower bound is too large: %d",
 141                                                         lb[i])));
 142         }
 143 }
 144
 145 /*
 146  * Compute ranges (sub-array dimensions) for an array slice
 147  *
 148  * We assume caller has validated slice endpoints, so overflow is impossible
 149  */
 150 void
 151 mda_get_range(int n, int *span, const int *st, const int *endp)
 152 {
 153         int                     i;
 154
 155         for (i = 0; i < n; i++)
 156                 span[i] = endp[i] - st[i] + 1;
 157 }
 158
 159 /*
 160  * Compute products of array dimensions, ie, scale factors for subscripts
 161  *
 162  * We assume caller has validated dimensions, so overflow is impossible
 163  */
 164 void
 165 mda_get_prod(int n, const int *range, int *prod)
 166 {
 167         int                     i;
 168
 169         prod[n - 1] = 1;
 170         for (i = n - 2; i >= 0; i--)
 171                 prod[i] = prod[i + 1] * range[i + 1];
 172 }
 173
 174 /*
 175  * From products of whole-array dimensions and spans of a sub-array,
 176  * compute offset distances needed to step through subarray within array
 177  *
 178  * We assume caller has validated dimensions, so overflow is impossible
 179  */
 180 void
 181 mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
 182 {
 183         int                     i,
 184                                 j;
 185
 186         dist[n - 1] = 0;
 187         for (j = n - 2; j >= 0; j--)
 188         {
 189                 dist[j] = prod[j] - 1;
 190                 for (i = j + 1; i < n; i++)
 191                         dist[j] -= (span[i] - 1) * prod[i];
 192         }
 193 }
 194
 195 /*
 196  * Generates the tuple that is lexicographically one greater than the current
 197  * n-tuple in "curr", with the restriction that the i-th element of "curr" is
 198  * less than the i-th element of "span".
 199  *
 200  * Returns -1 if no next tuple exists, else the subscript position (0..n-1)
 201  * corresponding to the dimension to advance along.
 202  *
 203  * We assume caller has validated dimensions, so overflow is impossible
 204  */
 205 int
 206 mda_next_tuple(int n, int *curr, const int *span)
 207 {
 208         int                     i;
 209
 210         if (n <= 0)
 211                 return -1;
 212
 213         curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
 214         for (i = n - 1; i && curr[i] == 0; i--)
 215                 curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
 216
 217         if (i)
 218                 return i;
 219         if (curr[0])
 220                 return 0;
 221
 222         return -1;
 223 }
 224
 225 /*
 226  * ArrayGetIntegerTypmods: verify that argument is a 1-D cstring array,
 227  * and get the contents converted to integers.  Returns a palloc'd array
 228  * and places the length at *n.
 229  */
 230 int32 *
 231 ArrayGetIntegerTypmods(ArrayType *arr, int *n)
 232 {
 233         int32      *result;
 234         Datum      *elem_values;
 235         int                     i;
 236
 237         if (ARR_ELEMTYPE(arr) != CSTRINGOID)
 238                 ereport(ERROR,
 239                                 (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
 240                                  errmsg("typmod array must be type cstring[]")));
 241
 242         if (ARR_NDIM(arr) != 1)
 243                 ereport(ERROR,
 244                                 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
 245                                  errmsg("typmod array must be one-dimensional")));
 246
 247         if (array_contains_nulls(arr))
 248                 ereport(ERROR,
 249                                 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 250                                  errmsg("typmod array must not contain nulls")));
 251
 252         /* hardwired knowledge about cstring's representation details here */
 253         deconstruct_array(arr, CSTRINGOID,
 254                                           -2, false, TYPALIGN_CHAR,
 255                                           &elem_values, NULL, n);
 256
 257         result = (int32 *) palloc(*n * sizeof(int32));
 258
 259         for (i = 0; i < *n; i++)
 260                 result[i] = pg_strtoint32(DatumGetCString(elem_values[i]));
 261
 262         pfree(elem_values);
 263
 264         return result;
 265 }