src/seq.c

   1 /* seq - print sequence of numbers to standard output.
   2    Copyright (C) 1994-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 /* Written by Ulrich Drepper.  */
  18
  19 #include <config.h>
  20 #include <getopt.h>
  21 #include <stdio.h>
  22 #include <sys/types.h>
  23
  24 #include "system.h"
  25 #include "die.h"
  26 #include "c-strtod.h"
  27 #include "error.h"
  28 #include "quote.h"
  29 #include "xstrtod.h"
  30
  31 /* Roll our own isfinite/isnan rather than using <math.h>, so that we don't
  32    have to worry about linking -lm just for isfinite.  */
  33 #ifndef isfinite
  34 # define isfinite(x) ((x) * 0 == 0)
  35 #endif
  36 #ifndef isnan
  37 # define isnan(x) ((x) != (x))
  38 #endif
  39
  40 /* The official name of this program (e.g., no 'g' prefix).  */
  41 #define PROGRAM_NAME "seq"
  42
  43 #define AUTHORS proper_name ("Ulrich Drepper")
  44
  45 /* If true print all number with equal width.  */
  46 static bool equal_width;
  47
  48 /* The string used to separate two numbers.  */
  49 static char const *separator;
  50
  51 /* The string output after all numbers have been output.
  52    Usually "\n" or "\0".  */
  53 static char const terminator[] = "\n";
  54
  55 static struct option const long_options[] =
  56 {
  57   { "equal-width", no_argument, NULL, 'w'},
  58   { "format", required_argument, NULL, 'f'},
  59   { "separator", required_argument, NULL, 's'},
  60   {GETOPT_HELP_OPTION_DECL},
  61   {GETOPT_VERSION_OPTION_DECL},
  62   { NULL, 0, NULL, 0}
  63 };
  64
  65 void
  66 usage (int status)
  67 {
  68   if (status != EXIT_SUCCESS)
  69     emit_try_help ();
  70   else
  71     {
  72       printf (_("\
  73 Usage: %s [OPTION]... LAST\n\
  74   or:  %s [OPTION]... FIRST LAST\n\
  75   or:  %s [OPTION]... FIRST INCREMENT LAST\n\
  76 "), program_name, program_name, program_name);
  77       fputs (_("\
  78 Print numbers from FIRST to LAST, in steps of INCREMENT.\n\
  79 "), stdout);
  80
  81       emit_mandatory_arg_note ();
  82
  83       fputs (_("\
  84   -f, --format=FORMAT      use printf style floating-point FORMAT\n\
  85   -s, --separator=STRING   use STRING to separate numbers (default: \\n)\n\
  86   -w, --equal-width        equalize width by padding with leading zeroes\n\
  87 "), stdout);
  88       fputs (HELP_OPTION_DESCRIPTION, stdout);
  89       fputs (VERSION_OPTION_DESCRIPTION, stdout);
  90       fputs (_("\
  91 \n\
  92 If FIRST or INCREMENT is omitted, it defaults to 1.  That is, an\n\
  93 omitted INCREMENT defaults to 1 even when LAST is smaller than FIRST.\n\
  94 The sequence of numbers ends when the sum of the current number and\n\
  95 INCREMENT would become greater than LAST.\n\
  96 FIRST, INCREMENT, and LAST are interpreted as floating point values.\n\
  97 INCREMENT is usually positive if FIRST is smaller than LAST, and\n\
  98 INCREMENT is usually negative if FIRST is greater than LAST.\n\
  99 INCREMENT must not be 0; none of FIRST, INCREMENT and LAST may be NaN.\n\
 100 "), stdout);
 101       fputs (_("\
 102 FORMAT must be suitable for printing one argument of type 'double';\n\
 103 it defaults to %.PRECf if FIRST, INCREMENT, and LAST are all fixed point\n\
 104 decimal numbers with maximum precision PREC, and to %g otherwise.\n\
 105 "), stdout);
 106       emit_ancillary_info (PROGRAM_NAME);
 107     }
 108   exit (status);
 109 }
 110
 111 /* A command-line operand.  */
 112 struct operand
 113 {
 114   /* Its value, converted to 'long double'.  */
 115   long double value;
 116
 117   /* Its print width, if it were printed out in a form similar to its
 118      input form.  An input like "-.1" is treated like "-0.1", and an
 119      input like "1." is treated like "1", but otherwise widths are
 120      left alone.  */
 121   size_t width;
 122
 123   /* Number of digits after the decimal point, or INT_MAX if the
 124      number can't easily be expressed as a fixed-point number.  */
 125   int precision;
 126 };
 127 typedef struct operand operand;
 128
 129 /* Description of what a number-generating format will generate.  */
 130 struct layout
 131 {
 132   /* Number of bytes before and after the number.  */
 133   size_t prefix_len;
 134   size_t suffix_len;
 135 };
 136
 137 /* Read a long double value from the command line.
 138    Return if the string is correct else signal error.  */
 139
 140 static operand
 141 scan_arg (const char *arg)
 142 {
 143   operand ret;
 144
 145   if (! xstrtold (arg, NULL, &ret.value, c_strtold))
 146     {
 147       error (0, 0, _("invalid floating point argument: %s"), quote (arg));
 148       usage (EXIT_FAILURE);
 149     }
 150
 151   if (isnan (ret.value))
 152     {
 153       error (0, 0, _("invalid %s argument: %s"), quote_n (0, "not-a-number"),
 154              quote_n (1, arg));
 155       usage (EXIT_FAILURE);
 156     }
 157
 158   /* We don't output spaces or '+' so don't include in width */
 159   while (isspace (to_uchar (*arg)) || *arg == '+')
 160     arg++;
 161
 162   /* Default to auto width and precision.  */
 163   ret.width = 0;
 164   ret.precision = INT_MAX;
 165
 166   /* Use no precision (and possibly fast generation) for integers.  */
 167   char const *decimal_point = strchr (arg, '.');
 168   if (! decimal_point && ! strchr (arg, 'p') /* not a hex float */)
 169     ret.precision = 0;
 170
 171   /* auto set width and precision for decimal inputs.  */
 172   if (! arg[strcspn (arg, "xX")] && isfinite (ret.value))
 173     {
 174       size_t fraction_len = 0;
 175       ret.width = strlen (arg);
 176
 177       if (decimal_point)
 178         {
 179           fraction_len = strcspn (decimal_point + 1, "eE");
 180           if (fraction_len <= INT_MAX)
 181             ret.precision = fraction_len;
 182           ret.width += (fraction_len == 0                      /* #.  -> #   */
 183                         ? -1
 184                         : (decimal_point == arg                /* .#  -> 0.# */
 185                            || ! ISDIGIT (decimal_point[-1]))); /* -.# -> 0.# */
 186         }
 187       char const *e = strchr (arg, 'e');
 188       if (! e)
 189         e = strchr (arg, 'E');
 190       if (e)
 191         {
 192           long exponent = strtol (e + 1, NULL, 10);
 193           ret.precision += exponent < 0 ? -exponent
 194                                         : - MIN (ret.precision, exponent);
 195           /* Don't account for e.... in the width since this is not output.  */
 196           ret.width -= strlen (arg) - (e - arg);
 197           /* Adjust the width as per the exponent.  */
 198           if (exponent < 0)
 199             {
 200               if (decimal_point)
 201                 {
 202                   if (e == decimal_point + 1) /* undo #. -> # above  */
 203                     ret.width++;
 204                 }
 205               else
 206                 ret.width++;
 207               exponent = -exponent;
 208             }
 209           else
 210             {
 211               if (decimal_point && ret.precision == 0 && fraction_len)
 212                 ret.width--; /* discount space for '.'  */
 213               exponent -= MIN (fraction_len, exponent);
 214             }
 215           ret.width += exponent;
 216         }
 217     }
 218
 219   return ret;
 220 }
 221
 222 /* If FORMAT is a valid printf format for a double argument, return
 223    its long double equivalent, allocated from dynamic storage, and
 224    store into *LAYOUT a description of the output layout; otherwise,
 225    report an error and exit.  */
 226
 227 static char const *
 228 long_double_format (char const *fmt, struct layout *layout)
 229 {
 230   size_t i;
 231   size_t prefix_len = 0;
 232   size_t suffix_len = 0;
 233   size_t length_modifier_offset;
 234   bool has_L;
 235
 236   for (i = 0; ! (fmt[i] == '%' && fmt[i + 1] != '%'); i += (fmt[i] == '%') + 1)
 237     {
 238       if (!fmt[i])
 239         die (EXIT_FAILURE, 0,
 240              _("format %s has no %% directive"), quote (fmt));
 241       prefix_len++;
 242     }
 243
 244   i++;
 245   i += strspn (fmt + i, "-+#0 '");
 246   i += strspn (fmt + i, "0123456789");
 247   if (fmt[i] == '.')
 248     {
 249       i++;
 250       i += strspn (fmt + i, "0123456789");
 251     }
 252
 253   length_modifier_offset = i;
 254   has_L = (fmt[i] == 'L');
 255   i += has_L;
 256   if (fmt[i] == '\0')
 257     die (EXIT_FAILURE, 0, _("format %s ends in %%"), quote (fmt));
 258   if (! strchr ("efgaEFGA", fmt[i]))
 259     die (EXIT_FAILURE, 0,
 260          _("format %s has unknown %%%c directive"), quote (fmt), fmt[i]);
 261
 262   for (i++; ; i += (fmt[i] == '%') + 1)
 263     if (fmt[i] == '%' && fmt[i + 1] != '%')
 264       die (EXIT_FAILURE, 0, _("format %s has too many %% directives"),
 265            quote (fmt));
 266     else if (fmt[i])
 267       suffix_len++;
 268     else
 269       {
 270         size_t format_size = i + 1;
 271         char *ldfmt = xmalloc (format_size + 1);
 272         memcpy (ldfmt, fmt, length_modifier_offset);
 273         ldfmt[length_modifier_offset] = 'L';
 274         strcpy (ldfmt + length_modifier_offset + 1,
 275                 fmt + length_modifier_offset + has_L);
 276         layout->prefix_len = prefix_len;
 277         layout->suffix_len = suffix_len;
 278         return ldfmt;
 279       }
 280 }
 281
 282 static void ATTRIBUTE_NORETURN
 283 io_error (void)
 284 {
 285   /* FIXME: consider option to silently ignore errno=EPIPE */
 286   clearerr (stdout);
 287   die (EXIT_FAILURE, errno, _("write error"));
 288 }
 289
 290 /* Actually print the sequence of numbers in the specified range, with the
 291    given or default stepping and format.  */
 292
 293 static void
 294 print_numbers (char const *fmt, struct layout layout,
 295                long double first, long double step, long double last)
 296 {
 297   bool out_of_range = (step < 0 ? first < last : last < first);
 298
 299   if (! out_of_range)
 300     {
 301       long double x = first;
 302       long double i;
 303
 304       for (i = 1; ; i++)
 305         {
 306           long double x0 = x;
 307           if (printf (fmt, x) < 0)
 308             io_error ();
 309           if (out_of_range)
 310             break;
 311           x = first + i * step;
 312           out_of_range = (step < 0 ? x < last : last < x);
 313
 314           if (out_of_range)
 315             {
 316               /* If the number just past LAST prints as a value equal
 317                  to LAST, and prints differently from the previous
 318                  number, then print the number.  This avoids problems
 319                  with rounding.  For example, with the x86 it causes
 320                  "seq 0 0.000001 0.000003" to print 0.000003 instead
 321                  of stopping at 0.000002.  */
 322
 323               bool print_extra_number = false;
 324               long double x_val;
 325               char *x_str;
 326               int x_strlen;
 327               setlocale (LC_NUMERIC, "C");
 328               x_strlen = asprintf (&x_str, fmt, x);
 329               setlocale (LC_NUMERIC, "");
 330               if (x_strlen < 0)
 331                 xalloc_die ();
 332               x_str[x_strlen - layout.suffix_len] = '\0';
 333
 334               if (xstrtold (x_str + layout.prefix_len, NULL, &x_val, c_strtold)
 335                   && x_val == last)
 336                 {
 337                   char *x0_str = NULL;
 338                   if (asprintf (&x0_str, fmt, x0) < 0)
 339                     xalloc_die ();
 340                   print_extra_number = !STREQ (x0_str, x_str);
 341                   free (x0_str);
 342                 }
 343
 344               free (x_str);
 345               if (! print_extra_number)
 346                 break;
 347             }
 348
 349           if (fputs (separator, stdout) == EOF)
 350             io_error ();
 351         }
 352
 353       if (fputs (terminator, stdout) == EOF)
 354         io_error ();
 355     }
 356 }
 357
 358 /* Return the default format given FIRST, STEP, and LAST.  */
 359 static char const *
 360 get_default_format (operand first, operand step, operand last)
 361 {
 362   static char format_buf[sizeof "%0.Lf" + 2 * INT_STRLEN_BOUND (int)];
 363
 364   int prec = MAX (first.precision, step.precision);
 365
 366   if (prec != INT_MAX && last.precision != INT_MAX)
 367     {
 368       if (equal_width)
 369         {
 370           /* increase first_width by any increased precision in step */
 371           size_t first_width = first.width + (prec - first.precision);
 372           /* adjust last_width to use precision from first/step */
 373           size_t last_width = last.width + (prec - last.precision);
 374           if (last.precision && prec == 0)
 375             last_width--;  /* don't include space for '.' */
 376           if (last.precision == 0 && prec)
 377             last_width++;  /* include space for '.' */
 378           if (first.precision == 0 && prec)
 379             first_width++;  /* include space for '.' */
 380           size_t width = MAX (first_width, last_width);
 381           if (width <= INT_MAX)
 382             {
 383               int w = width;
 384               sprintf (format_buf, "%%0%d.%dLf", w, prec);
 385               return format_buf;
 386             }
 387         }
 388       else
 389         {
 390           sprintf (format_buf, "%%.%dLf", prec);
 391           return format_buf;
 392         }
 393     }
 394
 395   return "%Lg";
 396 }
 397
 398 /* The NUL-terminated string S0 of length S_LEN represents a valid
 399    non-negative decimal integer.  Adjust the string and length so
 400    that the pair describe the next-larger value.  */
 401 static void
 402 incr (char **s0, size_t *s_len)
 403 {
 404   char *s = *s0;
 405   char *endp = s + *s_len - 1;
 406
 407   do
 408     {
 409       if ((*endp)++ < '9')
 410         return;
 411       *endp-- = '0';
 412     }
 413   while (endp >= s);
 414   *--(*s0) = '1';
 415   ++*s_len;
 416 }
 417
 418 /* Compare A and B (each a NUL-terminated digit string), with lengths
 419    given by A_LEN and B_LEN.  Return +1 if A < B, -1 if B < A, else 0.  */
 420 static int
 421 cmp (char const *a, size_t a_len, char const *b, size_t b_len)
 422 {
 423   if (a_len < b_len)
 424     return -1;
 425   if (b_len < a_len)
 426     return 1;
 427   return (strcmp (a, b));
 428 }
 429
 430 /* Trim leading 0's from S, but if S is all 0's, leave one.
 431    Return a pointer to the trimmed string.  */
 432 static char const * _GL_ATTRIBUTE_PURE
 433 trim_leading_zeros (char const *s)
 434 {
 435   char const *p = s;
 436   while (*s == '0')
 437     ++s;
 438
 439   /* If there were only 0's, back up, to leave one.  */
 440   if (!*s && s != p)
 441     --s;
 442   return s;
 443 }
 444
 445 /* Print all whole numbers from A to B, inclusive -- to stdout, each
 446    followed by a newline.  If B < A, return false and print nothing.
 447    Otherwise, return true.  */
 448 static bool
 449 seq_fast (char const *a, char const *b)
 450 {
 451   bool inf = STREQ (b, "inf");
 452
 453   /* Skip past any leading 0's.  Without this, our naive cmp
 454      function would declare 000 to be larger than 99.  */
 455   a = trim_leading_zeros (a);
 456   b = trim_leading_zeros (b);
 457
 458   size_t p_len = strlen (a);
 459   size_t q_len = inf ? 0 : strlen (b);
 460
 461   /* Allow for at least 31 digits without realloc.
 462      1 more than p_len is needed for the inf case.  */
 463   size_t inc_size = MAX (MAX (p_len + 1, q_len), 31);
 464
 465   /* Copy input strings (incl NUL) to end of new buffers.  */
 466   char *p0 = xmalloc (inc_size + 1);
 467   char *p = memcpy (p0 + inc_size - p_len, a, p_len + 1);
 468   char *q;
 469   char *q0;
 470   if (! inf)
 471     {
 472       q0 = xmalloc (inc_size + 1);
 473       q = memcpy (q0 + inc_size - q_len, b, q_len + 1);
 474     }
 475   else
 476     q = q0 = NULL;
 477
 478   bool ok = inf || cmp (p, p_len, q, q_len) <= 0;
 479   if (ok)
 480     {
 481       /* Reduce number of fwrite calls which is seen to
 482          give a speed-up of more than 2x over the unbuffered code
 483          when printing the first 10^9 integers.  */
 484       size_t buf_size = MAX (BUFSIZ, (inc_size + 1) * 2);
 485       char *buf = xmalloc (buf_size);
 486       char const *buf_end = buf + buf_size;
 487
 488       char *bufp = buf;
 489
 490       /* Write first number to buffer.  */
 491       bufp = mempcpy (bufp, p, p_len);
 492
 493       /* Append separator then number.  */
 494       while (inf || cmp (p, p_len, q, q_len) < 0)
 495         {
 496           *bufp++ = *separator;
 497           incr (&p, &p_len);
 498
 499           /* Double up the buffers when needed for the inf case.  */
 500           if (p_len == inc_size)
 501             {
 502               inc_size *= 2;
 503               p0 = xrealloc (p0, inc_size + 1);
 504               p = memmove (p0 + p_len, p0, p_len + 1);
 505
 506               if (buf_size < (inc_size + 1) * 2)
 507                 {
 508                   size_t buf_offset = bufp - buf;
 509                   buf_size = (inc_size + 1) * 2;
 510                   buf = xrealloc (buf, buf_size);
 511                   buf_end = buf + buf_size;
 512                   bufp = buf + buf_offset;
 513                 }
 514             }
 515
 516           bufp = mempcpy (bufp, p, p_len);
 517           /* If no place for another separator + number then
 518              output buffer so far, and reset to start of buffer.  */
 519           if (buf_end - (p_len + 1) < bufp)
 520             {
 521               if (fwrite (buf, bufp - buf, 1, stdout) != 1)
 522                 io_error ();
 523               bufp = buf;
 524             }
 525         }
 526
 527       /* Write any remaining buffered output, and the terminator.  */
 528       *bufp++ = *terminator;
 529       if (fwrite (buf, bufp - buf, 1, stdout) != 1)
 530         io_error ();
 531
 532       IF_LINT (free (buf));
 533     }
 534
 535   free (p0);
 536   free (q0);
 537   return ok;
 538 }
 539
 540 /* Return true if S consists of at least one digit and no non-digits.  */
 541 static bool _GL_ATTRIBUTE_PURE
 542 all_digits_p (char const *s)
 543 {
 544   size_t n = strlen (s);
 545   return ISDIGIT (s[0]) && n == strspn (s, "0123456789");
 546 }
 547
 548 int
 549 main (int argc, char **argv)
 550 {
 551   int optc;
 552   operand first = { 1, 1, 0 };
 553   operand step = { 1, 1, 0 };
 554   operand last;
 555   struct layout layout = { 0, 0 };
 556
 557   /* The printf(3) format used for output.  */
 558   char const *format_str = NULL;
 559
 560   initialize_main (&argc, &argv);
 561   set_program_name (argv[0]);
 562   setlocale (LC_ALL, "");
 563   bindtextdomain (PACKAGE, LOCALEDIR);
 564   textdomain (PACKAGE);
 565
 566   atexit (close_stdout);
 567
 568   equal_width = false;
 569   separator = "\n";
 570
 571   /* We have to handle negative numbers in the command line but this
 572      conflicts with the command line arguments.  So explicitly check first
 573      whether the next argument looks like a negative number.  */
 574   while (optind < argc)
 575     {
 576       if (argv[optind][0] == '-'
 577           && ((optc = argv[optind][1]) == '.' || ISDIGIT (optc)))
 578         {
 579           /* means negative number */
 580           break;
 581         }
 582
 583       optc = getopt_long (argc, argv, "+f:s:w", long_options, NULL);
 584       if (optc == -1)
 585         break;
 586
 587       switch (optc)
 588         {
 589         case 'f':
 590           format_str = optarg;
 591           break;
 592
 593         case 's':
 594           separator = optarg;
 595           break;
 596
 597         case 'w':
 598           equal_width = true;
 599           break;
 600
 601         case_GETOPT_HELP_CHAR;
 602
 603         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 604
 605         default:
 606           usage (EXIT_FAILURE);
 607         }
 608     }
 609
 610   unsigned int n_args = argc - optind;
 611   if (n_args < 1)
 612     {
 613       error (0, 0, _("missing operand"));
 614       usage (EXIT_FAILURE);
 615     }
 616
 617   if (3 < n_args)
 618     {
 619       error (0, 0, _("extra operand %s"), quote (argv[optind + 3]));
 620       usage (EXIT_FAILURE);
 621     }
 622
 623   if (format_str)
 624     format_str = long_double_format (format_str, &layout);
 625
 626   if (format_str != NULL && equal_width)
 627     {
 628       error (0, 0, _("format string may not be specified"
 629                      " when printing equal width strings"));
 630       usage (EXIT_FAILURE);
 631     }
 632
 633   /* If the following hold:
 634      - no format string, [FIXME: relax this, eventually]
 635      - integer start (or no start)
 636      - integer end
 637      - increment == 1 or not specified [FIXME: relax this, eventually]
 638      then use the much more efficient integer-only code.  */
 639   if (all_digits_p (argv[optind])
 640       && (n_args == 1 || all_digits_p (argv[optind + 1]))
 641       && (n_args < 3 || (STREQ ("1", argv[optind + 1])
 642                          && all_digits_p (argv[optind + 2])))
 643       && !equal_width && !format_str && strlen (separator) == 1)
 644     {
 645       char const *s1 = n_args == 1 ? "1" : argv[optind];
 646       char const *s2 = argv[optind + (n_args - 1)];
 647       if (seq_fast (s1, s2))
 648         return EXIT_SUCCESS;
 649
 650       /* Upon any failure, let the more general code deal with it.  */
 651     }
 652
 653   last = scan_arg (argv[optind++]);
 654
 655   if (optind < argc)
 656     {
 657       first = last;
 658       last = scan_arg (argv[optind++]);
 659
 660       if (optind < argc)
 661         {
 662           step = last;
 663           if (step.value == 0)
 664             {
 665               error (0, 0, _("invalid Zero increment value: %s"),
 666                      quote (argv[optind-1]));
 667               usage (EXIT_FAILURE);
 668             }
 669
 670           last = scan_arg (argv[optind++]);
 671         }
 672     }
 673
 674   if ((isfinite (first.value) && first.precision == 0)
 675       && step.precision == 0 && last.precision == 0
 676       && 0 <= first.value && step.value == 1 && 0 <= last.value
 677       && !equal_width && !format_str && strlen (separator) == 1)
 678     {
 679       char *s1;
 680       char *s2;
 681       if (asprintf (&s1, "%0.Lf", first.value) < 0)
 682         xalloc_die ();
 683       if (! isfinite (last.value))
 684         s2 = xstrdup ("inf"); /* Ensure "inf" is used.  */
 685       else if (asprintf (&s2, "%0.Lf", last.value) < 0)
 686         xalloc_die ();
 687
 688       if (*s1 != '-' && *s2 != '-' && seq_fast (s1, s2))
 689         {
 690           IF_LINT (free (s1));
 691           IF_LINT (free (s2));
 692           return EXIT_SUCCESS;
 693         }
 694
 695       free (s1);
 696       free (s2);
 697       /* Upon any failure, let the more general code deal with it.  */
 698     }
 699
 700   if (format_str == NULL)
 701     format_str = get_default_format (first, step, last);
 702
 703   print_numbers (format_str, layout, first.value, step.value, last.value);
 704
 705   return EXIT_SUCCESS;
 706 }