src/set-fields.c

   1 /* set-fields.c -- common functions for parsing field list
   2    Copyright (C) 2015-2025 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Extracted from cut.c by Assaf Gordon */
  18
  19 #include <config.h>
  20
  21 #include "system.h"
  22 #include <ctype.h>
  23 #include "c-ctype.h"
  24 #include "quote.h"
  25 #include "set-fields.h"
  26
  27 /* Array of `struct field_range_pair' holding all the finite ranges. */
  28 struct field_range_pair *frp;
  29
  30 /* Number of finite ranges specified by the user. */
  31 idx_t n_frp;
  32
  33 /* Number of `struct field_range_pair's allocated. */
  34 static idx_t n_frp_allocated;
  35
  36 #define FATAL_ERROR(Message)                                            \
  37   do                                                                    \
  38     {                                                                   \
  39       error (0, 0, (Message));                                          \
  40       usage (EXIT_FAILURE);                                             \
  41     }                                                                   \
  42   while (0)
  43
  44 /* Append LOW, HIGH to the list RP of range pairs, allocating additional
  45    space if necessary.  Update global variable N_FRP.  When allocating,
  46    update global variable N_FRP_ALLOCATED.  */
  47 static void
  48 add_range_pair (uintmax_t lo, uintmax_t hi)
  49 {
  50   if (n_frp == n_frp_allocated)
  51     frp = xpalloc (frp, &n_frp_allocated, 1, -1, sizeof *frp);
  52   frp[n_frp].lo = lo;
  53   frp[n_frp].hi = hi;
  54   ++n_frp;
  55 }
  56
  57
  58 /* Comparison function for qsort to order the list of
  59    struct field_range_pairs.  */
  60 static int
  61 compare_ranges (const void *a, const void *b)
  62 {
  63   struct field_range_pair const *ap = a, *bp = b;
  64   return (ap->lo > bp->lo) - (ap->lo < bp->lo);
  65 }
  66
  67 /* Reallocate Range Pair entries, with corresponding
  68    entries outside the range of each specified entry.  */
  69
  70 static void
  71 complement_rp (void)
  72 {
  73   struct field_range_pair *c = frp;
  74   idx_t n = n_frp;
  75
  76   frp = nullptr;
  77   n_frp = 0;
  78   n_frp_allocated = 0;
  79
  80   if (c[0].lo > 1)
  81     add_range_pair (1, c[0].lo - 1);
  82
  83   for (idx_t i = 1; i < n; ++i)
  84     {
  85       if (c[i - 1].hi + 1 == c[i].lo)
  86         continue;
  87
  88       add_range_pair (c[i - 1].hi + 1, c[i].lo - 1);
  89     }
  90
  91   if (c[n - 1].hi < UINTMAX_MAX)
  92     add_range_pair (c[n - 1].hi + 1, UINTMAX_MAX);
  93
  94   free (c);
  95 }
  96
  97 /* Given the list of field or byte range specifications FIELDSTR,
  98    allocate and initialize the FRP array. FIELDSTR should
  99    be composed of one or more numbers or ranges of numbers, separated
 100    by blanks or commas.  Incomplete ranges may be given: '-m' means '1-m';
 101    'n-' means 'n' through end of line.
 102    n=0 and n>=UINTMAX_MAX values will trigger an error.
 103
 104    if SETFLD_ALLOW_DASH option is used, a single '-' means all fields
 105    (otherwise a single dash triggers an error).
 106
 107    if SETFLD_COMPLEMENT option is used, the specified field list
 108    is complemented (e.g. '1-3' will result in fields '4-').
 109
 110    if SETFLD_ERRMSG_USE_POS option is used, error messages
 111    will say 'position' (or 'byte/character positions')
 112    instead of fields (used with cut -b/-c).
 113
 114    The function terminates on failure.
 115
 116    Upon return, the FRP array is initialized to contain
 117    a non-overlapping, increasing list of field ranges.
 118
 119    N_FRP holds the number of field ranges in the FRP array.
 120
 121    The first field is stored as 1 (zero is not used).
 122    An open-ended range (i.e., until the last field of the input line)
 123    is indicated with hi = UINTMAX_MAX.
 124
 125    A sentinel of UINTMAX_MAX/UINTMAX_MAX is always added as the last
 126    field range pair.
 127
 128    Examples:
 129    given '1-2,4', frp = [ { .lo = 1,           .hi = 2 },
 130                           { .lo = 4,           .hi = 4 },
 131                           { .lo = UINTMAX_MAX, .hi = UINTMAX_MAX } ];
 132
 133    given '3-',    frp = [ { .lo = 3,           .hi = UINTMAX_MAX },
 134                           { .lo = UINTMAX_MAX, .hi = UINTMAX_MAX } ];
 135 */
 136 void
 137 set_fields (char const *fieldstr, unsigned int options)
 138 {
 139   uintmax_t initial = 1;        /* Value of first number in a range.  */
 140   uintmax_t value = 0;          /* If nonzero, a number being accumulated.  */
 141   bool lhs_specified = false;
 142   bool rhs_specified = false;
 143   bool dash_found = false;      /* True if a '-' is found in this field.  */
 144
 145   bool in_digits = false;
 146
 147   /* Collect and store in RP the range end points. */
 148
 149   /* Special case: '--field=-' means all fields, emulate '--field=1-' . */
 150   if ((options & SETFLD_ALLOW_DASH) && STREQ (fieldstr,"-"))
 151     {
 152       value = 1;
 153       lhs_specified = true;
 154       dash_found = true;
 155       fieldstr++;
 156     }
 157
 158   while (true)
 159     {
 160       if (*fieldstr == '-')
 161         {
 162           in_digits = false;
 163           /* Starting a range. */
 164           if (dash_found)
 165             FATAL_ERROR ((options & SETFLD_ERRMSG_USE_POS)
 166                          ? _("invalid byte or character range")
 167                          : _("invalid field range"));
 168
 169           dash_found = true;
 170           fieldstr++;
 171
 172           if (lhs_specified && !value)
 173             FATAL_ERROR ((options & SETFLD_ERRMSG_USE_POS)
 174                          ? _("byte/character positions are numbered from 1")
 175                          : _("fields are numbered from 1"));
 176
 177           initial = (lhs_specified ? value : 1);
 178           value = 0;
 179         }
 180       else if (*fieldstr == ','
 181                || isblank (to_uchar (*fieldstr)) || *fieldstr == '\0')
 182         {
 183           in_digits = false;
 184           /* Ending the string, or this field/byte sublist. */
 185           if (dash_found)
 186             {
 187               dash_found = false;
 188
 189               if (!lhs_specified && !rhs_specified)
 190                 {
 191                   /* if a lone dash is allowed, emulate '1-' for all fields */
 192                   if (options & SETFLD_ALLOW_DASH)
 193                     initial = 1;
 194                   else
 195                     FATAL_ERROR (_("invalid range with no endpoint: -"));
 196                 }
 197
 198               /* A range.  Possibilities: -n, m-n, n-.
 199                  In any case, 'initial' contains the start of the range. */
 200               if (!rhs_specified)
 201                 {
 202                   /* 'n-'.  From 'initial' to end of line. */
 203                   add_range_pair (initial, UINTMAX_MAX);
 204                 }
 205               else
 206                 {
 207                   /* 'm-n' or '-n' (1-n). */
 208                   if (value < initial)
 209                     FATAL_ERROR (_("invalid decreasing range"));
 210
 211                   add_range_pair (initial, value);
 212                 }
 213               value = 0;
 214             }
 215           else
 216             {
 217               /* A simple field number, not a range. */
 218               if (value == 0)
 219                 FATAL_ERROR ((options & SETFLD_ERRMSG_USE_POS)
 220                              ? _("byte/character positions are numbered from 1")
 221                              : _("fields are numbered from 1"));
 222
 223               add_range_pair (value, value);
 224               value = 0;
 225             }
 226
 227           if (*fieldstr == '\0')
 228             break;
 229
 230           fieldstr++;
 231           lhs_specified = false;
 232           rhs_specified = false;
 233         }
 234       else if (c_isdigit (*fieldstr))
 235         {
 236           /* Record beginning of digit string, in case we have to
 237              complain about it.  */
 238           static char const *num_start;
 239           if (!in_digits || !num_start)
 240             num_start = fieldstr;
 241           in_digits = true;
 242
 243           if (dash_found)
 244             rhs_specified = 1;
 245           else
 246             lhs_specified = 1;
 247
 248           /* Detect overflow.  */
 249           if (!DECIMAL_DIGIT_ACCUMULATE (value, *fieldstr - '0')
 250               || value == UINTMAX_MAX)
 251             {
 252               /* In case the user specified -c$(echo 2^64|bc),22,
 253                  complain only about the first number.  */
 254               char *bad_num = ximemdup0 (num_start,
 255                                          strspn (num_start, "0123456789"));
 256               error (0, 0, (options & SETFLD_ERRMSG_USE_POS)
 257                            ?_("byte/character offset %s is too large")
 258                            :_("field number %s is too large"),
 259                            quote (bad_num));
 260               free (bad_num);
 261               usage (EXIT_FAILURE);
 262             }
 263
 264           fieldstr++;
 265         }
 266       else
 267         {
 268           error (0, 0, (options & SETFLD_ERRMSG_USE_POS)
 269                        ?_("invalid byte/character position %s")
 270                        :_("invalid field value %s"),
 271                        quote (fieldstr));
 272           usage (EXIT_FAILURE);
 273         }
 274     }
 275
 276   if (!n_frp)
 277     FATAL_ERROR ((options&SETFLD_ERRMSG_USE_POS)
 278                  ? _("missing list of byte/character positions")
 279                  : _("missing list of fields"));
 280
 281   qsort (frp, n_frp, sizeof (frp[0]), compare_ranges);
 282
 283   /* Merge range pairs (e.g. `2-5,3-4' becomes `2-5'). */
 284   for (idx_t i = 0; i < n_frp; ++i)
 285     {
 286       for (idx_t j = i + 1; j < n_frp; ++j)
 287         {
 288           if (frp[j].lo <= frp[i].hi)
 289             {
 290               frp[i].hi = MAX (frp[j].hi, frp[i].hi);
 291               memmove (frp + j, frp + j + 1, (n_frp - j - 1) * sizeof *frp);
 292               n_frp--;
 293               j--;
 294             }
 295           else
 296             break;
 297         }
 298     }
 299
 300   if (options & SETFLD_COMPLEMENT)
 301     complement_rp ();
 302
 303   /* After merging, reallocate RP so we release memory to the system.
 304      Also add a sentinel at the end of RP, to avoid out of bounds access
 305      and for performance reasons.  */
 306   ++n_frp;
 307   frp = xrealloc (frp, n_frp * sizeof (struct field_range_pair));
 308   frp[n_frp - 1].lo = frp[n_frp - 1].hi = UINTMAX_MAX;
 309 }