src/set-fields.c

   1 /* set-fields.c -- common functions for parsing field list
   2    Copyright (C) 2015-2024 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 "quote.h"
  24 #include "set-fields.h"
  25
  26 /* Array of `struct field_range_pair' holding all the finite ranges. */
  27 struct field_range_pair *frp;
  28
  29 /* Number of finite ranges specified by the user. */
  30 size_t n_frp;
  31
  32 /* Number of `struct field_range_pair's allocated. */
  33 static size_t n_frp_allocated;
  34
  35 #define FATAL_ERROR(Message)                                            \
  36   do                                                                    \
  37     {                                                                   \
  38       error (0, 0, (Message));                                          \
  39       usage (EXIT_FAILURE);                                             \
  40     }                                                                   \
  41   while (0)
  42
  43 /* Append LOW, HIGH to the list RP of range pairs, allocating additional
  44    space if necessary.  Update global variable N_FRP.  When allocating,
  45    update global variable N_FRP_ALLOCATED.  */
  46 static void
  47 add_range_pair (uintmax_t lo, uintmax_t hi)
  48 {
  49   if (n_frp == n_frp_allocated)
  50     frp = X2NREALLOC (frp, &n_frp_allocated);
  51   frp[n_frp].lo = lo;
  52   frp[n_frp].hi = hi;
  53   ++n_frp;
  54 }
  55
  56
  57 /* Comparison function for qsort to order the list of
  58    struct field_range_pairs.  */
  59 static int
  60 compare_ranges (const void *a, const void *b)
  61 {
  62   struct field_range_pair const *ap = a, *bp = b;
  63   return (ap->lo > bp->lo) - (ap->lo < bp->lo);
  64 }
  65
  66 /* Reallocate Range Pair entries, with corresponding
  67    entries outside the range of each specified entry.  */
  68
  69 static void
  70 complement_rp (void)
  71 {
  72   struct field_range_pair *c = frp;
  73   size_t n = n_frp;
  74
  75   frp = nullptr;
  76   n_frp = 0;
  77   n_frp_allocated = 0;
  78
  79   if (c[0].lo > 1)
  80     add_range_pair (1, c[0].lo - 1);
  81
  82   for (size_t i = 1; i < n; ++i)
  83     {
  84       if (c[i - 1].hi + 1 == c[i].lo)
  85         continue;
  86
  87       add_range_pair (c[i - 1].hi + 1, c[i].lo - 1);
  88     }
  89
  90   if (c[n - 1].hi < UINTMAX_MAX)
  91     add_range_pair (c[n - 1].hi + 1, UINTMAX_MAX);
  92
  93   free (c);
  94 }
  95
  96 /* Given the list of field or byte range specifications FIELDSTR,
  97    allocate and initialize the FRP array. FIELDSTR should
  98    be composed of one or more numbers or ranges of numbers, separated
  99    by blanks or commas.  Incomplete ranges may be given: '-m' means '1-m';
 100    'n-' means 'n' through end of line.
 101    n=0 and n>=UINTMAX_MAX values will trigger an error.
 102
 103    if SETFLD_ALLOW_DASH option is used, a single '-' means all fields
 104    (otherwise a single dash triggers an error).
 105
 106    if SETFLD_COMPLEMENT option is used, the specified field list
 107    is complemented (e.g. '1-3' will result in fields '4-').
 108
 109    if SETFLD_ERRMSG_USE_POS option is used, error messages
 110    will say 'position' (or 'byte/character positions')
 111    instead of fields (used with cut -b/-c).
 112
 113    The function terminates on failure.
 114
 115    Upon return, the FRP array is initialized to contain
 116    a non-overlapping, increasing list of field ranges.
 117
 118    N_FRP holds the number of field ranges in the FRP array.
 119
 120    The first field is stored as 1 (zero is not used).
 121    An open-ended range (i.e., until the last field of the input line)
 122    is indicated with hi = UINTMAX_MAX.
 123
 124    A sentinel of UINTMAX_MAX/UINTMAX_MAX is always added as the last
 125    field range pair.
 126
 127    Examples:
 128    given '1-2,4', frp = [ { .lo = 1,           .hi = 2 },
 129                           { .lo = 4,           .hi = 4 },
 130                           { .lo = UINTMAX_MAX, .hi = UINTMAX_MAX } ];
 131
 132    given '3-',    frp = [ { .lo = 3,           .hi = UINTMAX_MAX },
 133                           { .lo = UINTMAX_MAX, .hi = UINTMAX_MAX } ];
 134 */
 135 void
 136 set_fields (char const *fieldstr, unsigned int options)
 137 {
 138   uintmax_t initial = 1;        /* Value of first number in a range.  */
 139   uintmax_t value = 0;          /* If nonzero, a number being accumulated.  */
 140   bool lhs_specified = false;
 141   bool rhs_specified = false;
 142   bool dash_found = false;      /* True if a '-' is found in this field.  */
 143
 144   bool in_digits = false;
 145
 146   /* Collect and store in RP the range end points. */
 147
 148   /* Special case: '--field=-' means all fields, emulate '--field=1-' . */
 149   if ((options & SETFLD_ALLOW_DASH) && STREQ (fieldstr,"-"))
 150     {
 151       value = 1;
 152       lhs_specified = true;
 153       dash_found = true;
 154       fieldstr++;
 155     }
 156
 157   while (true)
 158     {
 159       if (*fieldstr == '-')
 160         {
 161           in_digits = false;
 162           /* Starting a range. */
 163           if (dash_found)
 164             FATAL_ERROR ((options & SETFLD_ERRMSG_USE_POS)
 165                          ? _("invalid byte or character range")
 166                          : _("invalid field range"));
 167
 168           dash_found = true;
 169           fieldstr++;
 170
 171           if (lhs_specified && !value)
 172             FATAL_ERROR ((options & SETFLD_ERRMSG_USE_POS)
 173                          ? _("byte/character positions are numbered from 1")
 174                          : _("fields are numbered from 1"));
 175
 176           initial = (lhs_specified ? value : 1);
 177           value = 0;
 178         }
 179       else if (*fieldstr == ','
 180                || isblank (to_uchar (*fieldstr)) || *fieldstr == '\0')
 181         {
 182           in_digits = false;
 183           /* Ending the string, or this field/byte sublist. */
 184           if (dash_found)
 185             {
 186               dash_found = false;
 187
 188               if (!lhs_specified && !rhs_specified)
 189                 {
 190                   /* if a lone dash is allowed, emulate '1-' for all fields */
 191                   if (options & SETFLD_ALLOW_DASH)
 192                     initial = 1;
 193                   else
 194                     FATAL_ERROR (_("invalid range with no endpoint: -"));
 195                 }
 196
 197               /* A range.  Possibilities: -n, m-n, n-.
 198                  In any case, 'initial' contains the start of the range. */
 199               if (!rhs_specified)
 200                 {
 201                   /* 'n-'.  From 'initial' to end of line. */
 202                   add_range_pair (initial, UINTMAX_MAX);
 203                 }
 204               else
 205                 {
 206                   /* 'm-n' or '-n' (1-n). */
 207                   if (value < initial)
 208                     FATAL_ERROR (_("invalid decreasing range"));
 209
 210                   add_range_pair (initial, value);
 211                 }
 212               value = 0;
 213             }
 214           else
 215             {
 216               /* A simple field number, not a range. */
 217               if (value == 0)
 218                 FATAL_ERROR ((options & SETFLD_ERRMSG_USE_POS)
 219                              ? _("byte/character positions are numbered from 1")
 220                              : _("fields are numbered from 1"));
 221
 222               add_range_pair (value, value);
 223               value = 0;
 224             }
 225
 226           if (*fieldstr == '\0')
 227             break;
 228
 229           fieldstr++;
 230           lhs_specified = false;
 231           rhs_specified = false;
 232         }
 233       else if (ISDIGIT (*fieldstr))
 234         {
 235           /* Record beginning of digit string, in case we have to
 236              complain about it.  */
 237           static char const *num_start;
 238           if (!in_digits || !num_start)
 239             num_start = fieldstr;
 240           in_digits = true;
 241
 242           if (dash_found)
 243             rhs_specified = 1;
 244           else
 245             lhs_specified = 1;
 246
 247           /* Detect overflow.  */
 248           if (!DECIMAL_DIGIT_ACCUMULATE (value, *fieldstr - '0')
 249               || value == UINTMAX_MAX)
 250             {
 251               /* In case the user specified -c$(echo 2^64|bc),22,
 252                  complain only about the first number.  */
 253               /* Determine the length of the offending number.  */
 254               size_t len = strspn (num_start, "0123456789");
 255               char *bad_num = ximemdup0 (num_start, len);
 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 (size_t i = 0; i < n_frp; ++i)
 285     {
 286       for (size_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 }