1/* Shuffle lines of text.
2
3   Copyright (C) 2006-2010 Free Software Foundation, Inc.
4
5   This program is free software: you can redistribute it and/or modify
6   it under the terms of the GNU General Public License as published by
7   the Free Software Foundation, either version 3 of the License, or
8   (at your option) any later version.
9
10   This program is distributed in the hope that it will be useful,
11   but WITHOUT ANY WARRANTY; without even the implied warranty of
12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13   GNU General Public License for more details.
14
15   You should have received a copy of the GNU General Public License
16   along with this program.  If not, see <http://www.gnu.org/licenses/>.
17
18   Written by Paul Eggert.  */
19
20#include <config.h>
21
22#include <sys/types.h>
23#include "system.h"
24
25#include "error.h"
26#include "getopt.h"
27#include "quote.h"
28#include "quotearg.h"
29#include "randint.h"
30#include "randperm.h"
31#include "stdio--.h"
32#include "xstrtol.h"
33
34/* The official name of this program (e.g., no `g' prefix).  */
35#define PROGRAM_NAME "shuf"
36
37#define AUTHORS proper_name ("Paul Eggert")
38
39void
40usage (int status)
41{
42  if (status != EXIT_SUCCESS)
43    fprintf (stderr, _("Try `%s --help' for more information.\n"),
44             program_name);
45  else
46    {
47      printf (_("\
48Usage: %s [OPTION]... [FILE]\n\
49  or:  %s -e [OPTION]... [ARG]...\n\
50  or:  %s -i LO-HI [OPTION]...\n\
51"),
52              program_name, program_name, program_name);
53      fputs (_("\
54Write a random permutation of the input lines to standard output.\n\
55\n\
56"), stdout);
57      fputs (_("\
58Mandatory arguments to long options are mandatory for short options too.\n\
59"), stdout);
60      fputs (_("\
61  -e, --echo                treat each ARG as an input line\n\
62  -i, --input-range=LO-HI   treat each number LO through HI as an input line\n\
63  -n, --head-count=COUNT    output at most COUNT lines\n\
64  -o, --output=FILE         write result to FILE instead of standard output\n\
65      --random-source=FILE  get random bytes from FILE\n\
66  -z, --zero-terminated     end lines with 0 byte, not newline\n\
67"), stdout);
68      fputs (HELP_OPTION_DESCRIPTION, stdout);
69      fputs (VERSION_OPTION_DESCRIPTION, stdout);
70      fputs (_("\
71\n\
72With no FILE, or when FILE is -, read standard input.\n\
73"), stdout);
74      emit_ancillary_info ();
75    }
76
77  exit (status);
78}
79
80/* For long options that have no equivalent short option, use a
81   non-character as a pseudo short option, starting with CHAR_MAX + 1.  */
82enum
83{
84  RANDOM_SOURCE_OPTION = CHAR_MAX + 1
85};
86
87static struct option const long_opts[] =
88{
89  {"echo", no_argument, NULL, 'e'},
90  {"input-range", required_argument, NULL, 'i'},
91  {"head-count", required_argument, NULL, 'n'},
92  {"output", required_argument, NULL, 'o'},
93  {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
94  {"zero-terminated", no_argument, NULL, 'z'},
95  {GETOPT_HELP_OPTION_DECL},
96  {GETOPT_VERSION_OPTION_DECL},
97  {0, 0, 0, 0},
98};
99
100static bool
101input_numbers_option_used (size_t lo_input, size_t hi_input)
102{
103  return ! (lo_input == SIZE_MAX && hi_input == 0);
104}
105
106static void
107input_from_argv (char **operand, int n_operands, char eolbyte)
108{
109  char *p;
110  size_t size = n_operands;
111  int i;
112
113  for (i = 0; i < n_operands; i++)
114    size += strlen (operand[i]);
115  p = xmalloc (size);
116
117  for (i = 0; i < n_operands; i++)
118    {
119      char *p1 = stpcpy (p, operand[i]);
120      operand[i] = p;
121      p = p1;
122      *p++ = eolbyte;
123    }
124
125  operand[n_operands] = p;
126}
127
128/* Return the start of the next line after LINE.  The current line
129   ends in EOLBYTE, and is guaranteed to end before LINE + N.  */
130
131static char *
132next_line (char *line, char eolbyte, size_t n)
133{
134  char *p = memchr (line, eolbyte, n);
135  return p + 1;
136}
137
138/* Read data from file IN.  Input lines are delimited by EOLBYTE;
139   silently append a trailing EOLBYTE if the file ends in some other
140   byte.  Store a pointer to the resulting array of lines into *PLINE.
141   Return the number of lines read.  Report an error and exit on
142   failure.  */
143
144static size_t
145read_input (FILE *in, char eolbyte, char ***pline)
146{
147  char *p;
148  char *buf = NULL;
149  char *lim;
150  size_t alloc = 0;
151  size_t used = 0;
152  size_t next_alloc = (1 << 13) + 1;
153  size_t bytes_to_read;
154  size_t nread;
155  char **line;
156  size_t i;
157  size_t n_lines;
158  int fread_errno;
159  struct stat instat;
160
161  if (fstat (fileno (in), &instat) == 0 && S_ISREG (instat.st_mode))
162    {
163      off_t file_size = instat.st_size;
164      off_t current_offset = ftello (in);
165      if (0 <= current_offset)
166        {
167          off_t remaining_size =
168            (current_offset < file_size ? file_size - current_offset : 0);
169          if (SIZE_MAX - 2 < remaining_size)
170            xalloc_die ();
171          next_alloc = remaining_size + 2;
172        }
173    }
174
175  do
176    {
177      if (alloc <= used + 1)
178        {
179          if (alloc == SIZE_MAX)
180            xalloc_die ();
181          alloc = next_alloc;
182          next_alloc = alloc * 2;
183          if (next_alloc < alloc)
184            next_alloc = SIZE_MAX;
185          buf = xrealloc (buf, alloc);
186        }
187
188      bytes_to_read = alloc - used - 1;
189      nread = fread (buf + used, sizeof (char), bytes_to_read, in);
190      used += nread;
191    }
192  while (nread == bytes_to_read);
193
194  fread_errno = errno;
195
196  if (used && buf[used - 1] != eolbyte)
197    buf[used++] = eolbyte;
198
199  lim = buf + used;
200
201  n_lines = 0;
202  for (p = buf; p < lim; p = next_line (p, eolbyte, lim - p))
203    n_lines++;
204
205  *pline = line = xnmalloc (n_lines + 1, sizeof *line);
206
207  line[0] = p = buf;
208  for (i = 1; i <= n_lines; i++)
209    line[i] = p = next_line (p, eolbyte, lim - p);
210
211  errno = fread_errno;
212  return n_lines;
213}
214
215static int
216write_permuted_output (size_t n_lines, char * const *line, size_t lo_input,
217                       size_t const *permutation, char eolbyte)
218{
219  size_t i;
220
221  if (line)
222    for (i = 0; i < n_lines; i++)
223      {
224        char * const *p = line + permutation[i];
225        size_t len = p[1] - p[0];
226        if (fwrite (p[0], sizeof *p[0], len, stdout) != len)
227          return -1;
228      }
229  else
230    for (i = 0; i < n_lines; i++)
231      {
232        unsigned long int n = lo_input + permutation[i];
233        if (printf ("%lu%c", n, eolbyte) < 0)
234          return -1;
235      }
236
237  return 0;
238}
239
240int
241main (int argc, char **argv)
242{
243  bool echo = false;
244  size_t lo_input = SIZE_MAX;
245  size_t hi_input = 0;
246  size_t head_lines = SIZE_MAX;
247  char const *outfile = NULL;
248  char *random_source = NULL;
249  char eolbyte = '\n';
250  char **input_lines = NULL;
251
252  int optc;
253  int n_operands;
254  char **operand;
255  size_t n_lines;
256  char **line;
257  struct randint_source *randint_source;
258  size_t *permutation;
259
260  initialize_main (&argc, &argv);
261  set_program_name (argv[0]);
262  setlocale (LC_ALL, "");
263  bindtextdomain (PACKAGE, LOCALEDIR);
264  textdomain (PACKAGE);
265
266  atexit (close_stdout);
267
268  while ((optc = getopt_long (argc, argv, "ei:n:o:z", long_opts, NULL)) != -1)
269    switch (optc)
270      {
271      case 'e':
272        echo = true;
273        break;
274
275      case 'i':
276        {
277          unsigned long int argval = 0;
278          char *p = strchr (optarg, '-');
279          char const *hi_optarg = optarg;
280          bool invalid = !p;
281
282          if (input_numbers_option_used (lo_input, hi_input))
283            error (EXIT_FAILURE, 0, _("multiple -i options specified"));
284
285          if (p)
286            {
287              *p = '\0';
288              invalid = ((xstrtoul (optarg, NULL, 10, &argval, NULL)
289                          != LONGINT_OK)
290                         || SIZE_MAX < argval);
291              *p = '-';
292              lo_input = argval;
293              hi_optarg = p + 1;
294            }
295
296          invalid |= ((xstrtoul (hi_optarg, NULL, 10, &argval, NULL)
297                       != LONGINT_OK)
298                      || SIZE_MAX < argval);
299          hi_input = argval;
300          n_lines = hi_input - lo_input + 1;
301          invalid |= ((lo_input <= hi_input) == (n_lines == 0));
302          if (invalid)
303            error (EXIT_FAILURE, 0, _("invalid input range %s"),
304                   quote (optarg));
305        }
306        break;
307
308      case 'n':
309        {
310          unsigned long int argval;
311          strtol_error e = xstrtoul (optarg, NULL, 10, &argval, NULL);
312
313          if (e == LONGINT_OK)
314            head_lines = MIN (head_lines, argval);
315          else if (e != LONGINT_OVERFLOW)
316            error (EXIT_FAILURE, 0, _("invalid line count %s"),
317                   quote (optarg));
318        }
319        break;
320
321      case 'o':
322        if (outfile && !STREQ (outfile, optarg))
323          error (EXIT_FAILURE, 0, _("multiple output files specified"));
324        outfile = optarg;
325        break;
326
327      case RANDOM_SOURCE_OPTION:
328        if (random_source && !STREQ (random_source, optarg))
329          error (EXIT_FAILURE, 0, _("multiple random sources specified"));
330        random_source = optarg;
331        break;
332
333      case 'z':
334        eolbyte = '\0';
335        break;
336
337      case_GETOPT_HELP_CHAR;
338      case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
339      default:
340        usage (EXIT_FAILURE);
341      }
342
343  n_operands = argc - optind;
344  operand = argv + optind;
345
346  if (echo)
347    {
348      if (input_numbers_option_used (lo_input, hi_input))
349        error (EXIT_FAILURE, 0, _("cannot combine -e and -i options"));
350      input_from_argv (operand, n_operands, eolbyte);
351      n_lines = n_operands;
352      line = operand;
353    }
354  else if (input_numbers_option_used (lo_input, hi_input))
355    {
356      if (n_operands)
357        {
358          error (0, 0, _("extra operand %s\n"), quote (operand[0]));
359          usage (EXIT_FAILURE);
360        }
361      n_lines = hi_input - lo_input + 1;
362      line = NULL;
363    }
364  else
365    {
366      switch (n_operands)
367        {
368        case 0:
369          break;
370
371        case 1:
372          if (! (STREQ (operand[0], "-") || freopen (operand[0], "r", stdin)))
373            error (EXIT_FAILURE, errno, "%s", operand[0]);
374          break;
375
376        default:
377          error (0, 0, _("extra operand %s"), quote (operand[1]));
378          usage (EXIT_FAILURE);
379        }
380
381      n_lines = read_input (stdin, eolbyte, &input_lines);
382      line = input_lines;
383    }
384
385  head_lines = MIN (head_lines, n_lines);
386
387  randint_source = randint_all_new (random_source,
388                                    randperm_bound (head_lines, n_lines));
389  if (! randint_source)
390    error (EXIT_FAILURE, errno, "%s", quotearg_colon (random_source));
391
392  /* Close stdin now, rather than earlier, so that randint_all_new
393     doesn't have to worry about opening something other than
394     stdin.  */
395  if (! (echo || input_numbers_option_used (lo_input, hi_input))
396      && (ferror (stdin) || fclose (stdin) != 0))
397    error (EXIT_FAILURE, errno, _("read error"));
398
399  permutation = randperm_new (randint_source, head_lines, n_lines);
400
401  if (outfile && ! freopen (outfile, "w", stdout))
402    error (EXIT_FAILURE, errno, "%s", quotearg_colon (outfile));
403  if (write_permuted_output (head_lines, line, lo_input, permutation, eolbyte)
404      != 0)
405    error (EXIT_FAILURE, errno, _("write error"));
406
407#ifdef lint
408  free (permutation);
409  randint_all_free (randint_source);
410  if (input_lines)
411    {
412      free (input_lines[0]);
413      free (input_lines);
414    }
415#endif
416
417  return EXIT_SUCCESS;
418}
419