src/set-fields.c

   1 /* set-fields.c -- common functions for parsing field list
   2    Copyright (C) 2015-2017 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 "error.h"
  23 #include "quote.h"
  24 #include "xstrndup.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 size_t n_frp;
  32
  33 /* Number of `struct field_range_pair's allocated. */
  34 static size_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 (size_t lo, size_t hi)
  49 {
  50   if (n_frp == n_frp_allocated)
  51     frp = X2NREALLOC (frp, &n_frp_allocated);
  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 range_pairs.  */
  60 static int
  61 compare_ranges (const void *a, const void *b)
  62 {
  63   int a_start = ((const struct field_range_pair *) a)->lo;
  64   int b_start = ((const struct field_range_pair *) b)->lo;
  65   return a_start < b_start ? -1 : a_start > b_start;
  66 }
  67
  68 /* Reallocate Range Pair entries, with corresponding
  69    entries outside the range of each specified entry.  */
  70
  71 static void
  72 complement_rp (void)
  73 {
  74   struct field_range_pair *c = frp;
  75   size_t n = n_frp;
  76
  77   frp = NULL;
  78   n_frp = 0;
  79   n_frp_allocated = 0;
  80
  81   if (c[0].lo > 1)
  82     add_range_pair (1, c[0].lo - 1);
  83
  84   for (size_t i = 1; i < n; ++i)
  85     {
  86       if (c[i-1].hi + 1 == c[i].lo)
  87         continue;
  88
  89       add_range_pair (c[i-1].hi + 1, c[i].lo - 1);
  90     }
  91
  92   if (c[n-1].hi < SIZE_MAX)
  93     add_range_pair (c[n-1].hi + 1, SIZE_MAX);
  94
  95   free (c);
  96 }
  97
  98 /* Given the list of field or byte range specifications FIELDSTR,
  99    allocate and initialize the FRP array. FIELDSTR should
 100    be composed of one or more numbers or ranges of numbers, separated
 101    by blanks or commas.  Incomplete ranges may be given: '-m' means '1-m';
 102    'n-' means 'n' through end of line.
 103    n=0 and n>=SIZE_MAX values will trigger an error.
 104
 105    if SETFLD_ALLOW_DASH option is used, a single '-' means all fields
 106    (otherwise a single dash triggers an error).
 107
 108    if SETFLD_COMPLEMENT option is used, the specified field list
 109    is complemented (e.g. '1-3' will result in fields '4-').
 110
 111    if SETFLD_ERRMSG_USE_POS option is used, error messages
 112    will say 'position' (or 'byte/character positions')
 113    instead of fields (used with cut -b/-c).
 114
 115    The function terminates on failure.
 116
 117    Upon return, the FRP array is initialized to contain
 118    a non-overlapping, increasing list of field ranges.
 119
 120    N_FRP holds the number of field ranges in the FRP array.
 121
 122    The first field is stored as 1 (zero is not used).
 123    An open-ended range (i.e., until the last field of the input line)
 124    is indicated with hi = SIZE_MAX.
 125
 126    A sentinel of SIZE_MAX/SIZE_MAX is always added as the last
 127    field range pair.
 128
 129    Examples:
 130    given '1-2,4', frp = [ { .lo = 1,        .hi = 2 },
 131                           { .lo = 4,        .hi = 4 },
 132                           { .lo = SIZE_MAX, .hi = SIZE_MAX } ];
 133
 134    given '3-',    frp = [ { .lo = 3,        .hi = SIZE_MAX },
 135                           { .lo = SIZE_MAX, .hi = SIZE_MAX } ];
 136 */
 137 void
 138 set_fields (const char *fieldstr, unsigned int options)
 139 {
 140   size_t initial = 1;           /* Value of first number in a range.  */
 141   size_t value = 0;             /* If nonzero, a number being accumulated.  */
 142   bool lhs_specified = false;
 143   bool rhs_specified = false;
 144   bool dash_found = false;      /* True if a '-' is found in this field.  */
 145
 146   bool in_digits = false;
 147
 148   /* Collect and store in RP the range end points. */
 149
 150   /* Special case: '--field=-' means all fields, emulate '--field=1-' . */
 151   if ((options & SETFLD_ALLOW_DASH) && STREQ (fieldstr,"-"))
 152     {
 153       value = 1;
 154       lhs_specified = true;
 155       dash_found = true;
 156       fieldstr++;
 157     }
 158
 159   while (true)
 160     {
 161       if (*fieldstr == '-')
 162         {
 163           in_digits = false;
 164           /* Starting a range. */
 165           if (dash_found)
 166             FATAL_ERROR ( (options & SETFLD_ERRMSG_USE_POS)
 167                           ?_("invalid byte or character range")
 168                           :_("invalid field range"));
 169
 170           dash_found = true;
 171           fieldstr++;
 172
 173           if (lhs_specified && !value)
 174             FATAL_ERROR ( (options & SETFLD_ERRMSG_USE_POS)
 175                           ?_("byte/character positions are numbered from 1")
 176                           :_("fields are numbered from 1"));
 177
 178           initial = (lhs_specified ? value : 1);
 179           value = 0;
 180         }
 181       else if (*fieldstr == ','
 182                || isblank (to_uchar (*fieldstr)) || *fieldstr == '\0')
 183         {
 184           in_digits = false;
 185           /* Ending the string, or this field/byte sublist. */
 186           if (dash_found)
 187             {
 188               dash_found = false;
 189
 190               if (!lhs_specified && !rhs_specified)
 191                 {
 192                   /* if a lone dash is allowed, emulate '1-' for all fields */
 193                   if (options & SETFLD_ALLOW_DASH)
 194                     initial = 1;
 195                   else
 196                     FATAL_ERROR (_("invalid range with no endpoint: -"));
 197                 }
 198
 199               /* A range.  Possibilities: -n, m-n, n-.
 200                  In any case, 'initial' contains the start of the range. */
 201               if (!rhs_specified)
 202                 {
 203                   /* 'n-'.  From 'initial' to end of line. */
 204                   add_range_pair (initial, SIZE_MAX);
 205                 }
 206               else
 207                 {
 208                   /* 'm-n' or '-n' (1-n). */
 209                   if (value < initial)
 210                     FATAL_ERROR (_("invalid decreasing range"));
 211
 212                   add_range_pair (initial, value);
 213                 }
 214               value = 0;
 215             }
 216           else
 217             {
 218               /* A simple field number, not a range. */
 219               if (value == 0)
 220                 FATAL_ERROR ( (options & SETFLD_ERRMSG_USE_POS)
 221                               ?_("byte/character positions are numbered from 1")
 222                               :_("fields are numbered from 1"));
 223
 224               add_range_pair (value, value);
 225               value = 0;
 226             }
 227
 228           if (*fieldstr == '\0')
 229             break;
 230
 231           fieldstr++;
 232           lhs_specified = false;
 233           rhs_specified = false;
 234         }
 235       else if (ISDIGIT (*fieldstr))
 236         {
 237           /* Record beginning of digit string, in case we have to
 238              complain about it.  */
 239           static char const *num_start;
 240           if (!in_digits || !num_start)
 241             num_start = fieldstr;
 242           in_digits = true;
 243
 244           if (dash_found)
 245             rhs_specified = 1;
 246           else
 247             lhs_specified = 1;
 248
 249           /* Detect overflow.  */
 250           if (!DECIMAL_DIGIT_ACCUMULATE (value, *fieldstr - '0', size_t)
 251               || value == SIZE_MAX)
 252             {
 253               /* In case the user specified -c$(echo 2^64|bc),22,
 254                  complain only about the first number.  */
 255               /* Determine the length of the offending number.  */
 256               size_t len = strspn (num_start, "0123456789");
 257               char *bad_num = xstrndup (num_start, len);
 258               error (0, 0, (options & SETFLD_ERRMSG_USE_POS)
 259                            ?_("byte/character offset %s is too large")
 260                            :_("field number %s is too large"),
 261                            quote (bad_num));
 262               free (bad_num);
 263               usage (EXIT_FAILURE);
 264             }
 265
 266           fieldstr++;
 267         }
 268       else
 269         {
 270           error (0, 0, (options & SETFLD_ERRMSG_USE_POS)
 271                        ?_("invalid byte/character position %s")
 272                        :_("invalid field value %s"),
 273                        quote (fieldstr));
 274           usage (EXIT_FAILURE);
 275         }
 276     }
 277
 278   if (!n_frp)
 279     FATAL_ERROR ( (options&SETFLD_ERRMSG_USE_POS)
 280                   ?_("missing list of byte/character positions")
 281                   :_("missing list of fields"));
 282
 283   qsort (frp, n_frp, sizeof (frp[0]), compare_ranges);
 284
 285   /* Merge range pairs (e.g. `2-5,3-4' becomes `2-5'). */
 286   for (size_t i = 0; i < n_frp; ++i)
 287     {
 288       for (size_t j = i + 1; j < n_frp; ++j)
 289         {
 290           if (frp[j].lo <= frp[i].hi)
 291             {
 292               frp[i].hi = MAX (frp[j].hi, frp[i].hi);
 293               memmove (frp + j, frp + j + 1, (n_frp - j - 1) * sizeof *frp);
 294               n_frp--;
 295               j--;
 296             }
 297           else
 298             break;
 299         }
 300     }
 301
 302   if (options & SETFLD_COMPLEMENT)
 303     complement_rp ();
 304
 305   /* After merging, reallocate RP so we release memory to the system.
 306      Also add a sentinel at the end of RP, to avoid out of bounds access
 307      and for performance reasons.  */
 308   ++n_frp;
 309   frp = xrealloc (frp, n_frp * sizeof (struct field_range_pair));
 310   frp[n_frp - 1].lo = frp[n_frp - 1].hi = SIZE_MAX;
 311 }
 312
 313 void
 314 reset_fields (void)
 315 {
 316   n_frp = 0 ;
 317   n_frp_allocated = 0;
 318   free (frp);
 319   frp = NULL;
 320 }