src/tac.c

   1 /* tac - concatenate and print files in reverse
   2    Copyright (C) 1988-1991, 1995-2001 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 2, or (at your option)
   7    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, write to the Free Software Foundation,
  16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  17
  18 /* Written by Jay Lepreau (lepreau@cs.utah.edu).
  19    GNU enhancements by David MacKenzie (djm@gnu.ai.mit.edu). */
  20
  21 /* Copy each FILE, or the standard input if none are given or when a
  22    FILE name of "-" is encountered, to the standard output with the
  23    order of the records reversed.  The records are separated by
  24    instances of a string, or a newline if none is given.  By default, the
  25    separator string is attached to the end of the record that it
  26    follows in the file.
  27
  28    Options:
  29    -b, --before                 The separator is attached to the beginning
  30                                 of the record that it precedes in the file.
  31    -r, --regex                  The separator is a regular expression.
  32    -s, --separator=separator    Use SEPARATOR as the record separator.
  33
  34    To reverse a file byte by byte, use (in bash, ksh, or sh):
  35 tac -r -s '.\|
  36 ' file */
  37
  38 #include <config.h>
  39
  40 #include <stdio.h>
  41 #include <getopt.h>
  42 #include <sys/types.h>
  43 #include "system.h"
  44 #include "closeout.h"
  45
  46 #include <regex.h>
  47
  48 #include "error.h"
  49 #include "safe-read.h"
  50
  51 /* The official name of this program (e.g., no `g' prefix).  */
  52 #define PROGRAM_NAME "tac"
  53
  54 #define AUTHORS N_ ("Jay Lepreau and David MacKenzie")
  55
  56 #if defined __MSDOS__ || defined _WIN32
  57 /* Define this to non-zero on systems for which the regular mechanism
  58    (of unlinking an open file and expecting to be able to write, seek
  59    back to the beginning, then reread it) doesn't work.  E.g., on Windows
  60    and DOS systems.  */
  61 # define DONT_UNLINK_WHILE_OPEN 1
  62 #endif
  63
  64
  65 #ifndef DEFAULT_TMPDIR
  66 # define DEFAULT_TMPDIR "/tmp"
  67 #endif
  68
  69 /* The number of bytes per atomic read. */
  70 #define INITIAL_READSIZE 8192
  71
  72 /* The number of bytes per atomic write. */
  73 #define WRITESIZE 8192
  74
  75 /* The name this program was run with. */
  76 char *program_name;
  77
  78 /* The string that separates the records of the file. */
  79 static char *separator;
  80
  81 /* If nonzero, print `separator' along with the record preceding it
  82    in the file; otherwise with the record following it. */
  83 static int separator_ends_record;
  84
  85 /* 0 if `separator' is to be matched as a regular expression;
  86    otherwise, the length of `separator', used as a sentinel to
  87    stop the search. */
  88 static int sentinel_length;
  89
  90 /* The length of a match with `separator'.  If `sentinel_length' is 0,
  91    `match_length' is computed every time a match succeeds;
  92    otherwise, it is simply the length of `separator'. */
  93 static int match_length;
  94
  95 /* The input buffer. */
  96 static char *G_buffer;
  97
  98 /* The number of bytes to read at once into `buffer'. */
  99 static size_t read_size;
 100
 101 /* The size of `buffer'.  This is read_size * 2 + sentinel_length + 2.
 102    The extra 2 bytes allow `past_end' to have a value beyond the
 103    end of `G_buffer' and `match_start' to run off the front of `G_buffer'. */
 104 static unsigned G_buffer_size;
 105
 106 /* The compiled regular expression representing `separator'. */
 107 static struct re_pattern_buffer compiled_separator;
 108
 109 static struct option const longopts[] =
 110 {
 111   {"before", no_argument, NULL, 'b'},
 112   {"regex", no_argument, NULL, 'r'},
 113   {"separator", required_argument, NULL, 's'},
 114   {GETOPT_HELP_OPTION_DECL},
 115   {GETOPT_VERSION_OPTION_DECL},
 116   {NULL, 0, NULL, 0}
 117 };
 118
 119 void
 120 usage (int status)
 121 {
 122   if (status != 0)
 123     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 124              program_name);
 125   else
 126     {
 127       printf (_("\
 128 Usage: %s [OPTION]... [FILE]...\n\
 129 "),
 130               program_name);
 131       fputs (_("\
 132 Write each FILE to standard output, last line first.\n\
 133 With no FILE, or when FILE is -, read standard input.\n\
 134 \n\
 135 "), stdout);
 136       fputs (_("\
 137 Mandatory arguments to long options are mandatory for short options too.\n\
 138 "), stdout);
 139       fputs (_("\
 140   -b, --before             attach the separator before instead of after\n\
 141   -r, --regex              interpret the separator as a regular expression\n\
 142   -s, --separator=STRING   use STRING as the separator instead of newline\n\
 143 "), stdout);
 144       fputs (_("\
 145       --help               display this help and exit\n\
 146       --version            output version information and exit\n\
 147 "), stdout);
 148       puts (_("\nReport bugs to <bug-textutils@gnu.org>."));
 149     }
 150   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 151 }
 152
 153 /* Print the characters from START to PAST_END - 1.
 154    If START is NULL, just flush the buffer. */
 155
 156 static void
 157 output (const char *start, const char *past_end)
 158 {
 159   static char buffer[WRITESIZE];
 160   static int bytes_in_buffer = 0;
 161   int bytes_to_add = past_end - start;
 162   int bytes_available = WRITESIZE - bytes_in_buffer;
 163
 164   if (start == 0)
 165     {
 166       fwrite (buffer, 1, bytes_in_buffer, stdout);
 167       bytes_in_buffer = 0;
 168       return;
 169     }
 170
 171   /* Write out as many full buffers as possible. */
 172   while (bytes_to_add >= bytes_available)
 173     {
 174       memcpy (buffer + bytes_in_buffer, start, bytes_available);
 175       bytes_to_add -= bytes_available;
 176       start += bytes_available;
 177       fwrite (buffer, 1, WRITESIZE, stdout);
 178       bytes_in_buffer = 0;
 179       bytes_available = WRITESIZE;
 180     }
 181
 182   memcpy (buffer + bytes_in_buffer, start, bytes_to_add);
 183   bytes_in_buffer += bytes_to_add;
 184 }
 185
 186 /* Print in reverse the file open on descriptor FD for reading FILE.
 187    Return 0 if ok, 1 if an error occurs. */
 188
 189 static int
 190 tac_seekable (int input_fd, const char *file)
 191 {
 192   /* Pointer to the location in `G_buffer' where the search for
 193      the next separator will begin. */
 194   char *match_start;
 195
 196   /* Pointer to one past the rightmost character in `G_buffer' that
 197      has not been printed yet. */
 198   char *past_end;
 199
 200   /* Length of the record growing in `G_buffer'. */
 201   size_t saved_record_size;
 202
 203   /* Offset in the file of the next read. */
 204   off_t file_pos;
 205
 206   /* Nonzero if `output' has not been called yet for any file.
 207      Only used when the separator is attached to the preceding record. */
 208   int first_time = 1;
 209   char first_char = *separator; /* Speed optimization, non-regexp. */
 210   char *separator1 = separator + 1; /* Speed optimization, non-regexp. */
 211   int match_length1 = match_length - 1; /* Speed optimization, non-regexp. */
 212   struct re_registers regs;
 213
 214   /* Find the size of the input file. */
 215   file_pos = lseek (input_fd, (off_t) 0, SEEK_END);
 216   if (file_pos < 1)
 217     return 0;                   /* It's an empty file. */
 218
 219   /* Arrange for the first read to lop off enough to leave the rest of the
 220      file a multiple of `read_size'.  Since `read_size' can change, this may
 221      not always hold during the program run, but since it usually will, leave
 222      it here for i/o efficiency (page/sector boundaries and all that).
 223      Note: the efficiency gain has not been verified. */
 224   saved_record_size = file_pos % read_size;
 225   if (saved_record_size == 0)
 226     saved_record_size = read_size;
 227   file_pos -= saved_record_size;
 228   /* `file_pos' now points to the start of the last (probably partial) block
 229      in the input file. */
 230
 231   if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 232     error (0, errno, "%s: seek failed", file);
 233
 234   if (safe_read (input_fd, G_buffer, saved_record_size) != saved_record_size)
 235     {
 236       error (0, errno, "%s", file);
 237       return 1;
 238     }
 239
 240   match_start = past_end = G_buffer + saved_record_size;
 241   /* For non-regexp search, move past impossible positions for a match. */
 242   if (sentinel_length)
 243     match_start -= match_length1;
 244
 245   for (;;)
 246     {
 247       /* Search backward from `match_start' - 1 to `G_buffer' for a match
 248          with `separator'; for speed, use strncmp if `separator' contains no
 249          metacharacters.
 250          If the match succeeds, set `match_start' to point to the start of
 251          the match and `match_length' to the length of the match.
 252          Otherwise, make `match_start' < `G_buffer'. */
 253       if (sentinel_length == 0)
 254         {
 255           int i = match_start - G_buffer;
 256           int ret;
 257
 258           ret = re_search (&compiled_separator, G_buffer, i, i - 1, -i, &regs);
 259           if (ret == -1)
 260             match_start = G_buffer - 1;
 261           else if (ret == -2)
 262             {
 263               error (EXIT_FAILURE, 0,
 264                      _("error in regular expression search"));
 265             }
 266           else
 267             {
 268               match_start = G_buffer + regs.start[0];
 269               match_length = regs.end[0] - regs.start[0];
 270             }
 271         }
 272       else
 273         {
 274           /* `match_length' is constant for non-regexp boundaries. */
 275           while (*--match_start != first_char
 276                  || (match_length1 && strncmp (match_start + 1, separator1,
 277                                                match_length1)))
 278             /* Do nothing. */ ;
 279         }
 280
 281       /* Check whether we backed off the front of `G_buffer' without finding
 282          a match for `separator'. */
 283       if (match_start < G_buffer)
 284         {
 285           if (file_pos == 0)
 286             {
 287               /* Hit the beginning of the file; print the remaining record. */
 288               output (G_buffer, past_end);
 289               return 0;
 290             }
 291
 292           saved_record_size = past_end - G_buffer;
 293           if (saved_record_size > read_size)
 294             {
 295               /* `G_buffer_size' is about twice `read_size', so since
 296                  we want to read in another `read_size' bytes before
 297                  the data already in `G_buffer', we need to increase
 298                  `G_buffer_size'. */
 299               char *newbuffer;
 300               int offset = sentinel_length ? sentinel_length : 1;
 301
 302               read_size *= 2;
 303               G_buffer_size = read_size * 2 + sentinel_length + 2;
 304               newbuffer = xrealloc (G_buffer - offset, G_buffer_size);
 305               newbuffer += offset;
 306               /* Adjust the pointers for the new buffer location.  */
 307               match_start += newbuffer - G_buffer;
 308               past_end += newbuffer - G_buffer;
 309               G_buffer = newbuffer;
 310             }
 311
 312           /* Back up to the start of the next bufferfull of the file.  */
 313           if (file_pos >= read_size)
 314             file_pos -= read_size;
 315           else
 316             {
 317               read_size = file_pos;
 318               file_pos = 0;
 319             }
 320           lseek (input_fd, file_pos, SEEK_SET);
 321
 322           /* Shift the pending record data right to make room for the new.
 323              The source and destination regions probably overlap.  */
 324           memmove (G_buffer + read_size, G_buffer, saved_record_size);
 325           past_end = G_buffer + read_size + saved_record_size;
 326           /* For non-regexp searches, avoid unneccessary scanning. */
 327           if (sentinel_length)
 328             match_start = G_buffer + read_size;
 329           else
 330             match_start = past_end;
 331
 332           if (safe_read (input_fd, G_buffer, read_size) != read_size)
 333             {
 334               error (0, errno, "%s", file);
 335               return 1;
 336             }
 337         }
 338       else
 339         {
 340           /* Found a match of `separator'. */
 341           if (separator_ends_record)
 342             {
 343               char *match_end = match_start + match_length;
 344
 345               /* If this match of `separator' isn't at the end of the
 346                  file, print the record. */
 347               if (first_time == 0 || match_end != past_end)
 348                 output (match_end, past_end);
 349               past_end = match_end;
 350               first_time = 0;
 351             }
 352           else
 353             {
 354               output (match_start, past_end);
 355               past_end = match_start;
 356             }
 357
 358           /* For non-regex matching, we can back up.  */
 359           if (sentinel_length > 0)
 360             match_start -= match_length - 1;
 361         }
 362     }
 363 }
 364
 365 /* Print FILE in reverse.
 366    Return 0 if ok, 1 if an error occurs. */
 367
 368 static int
 369 tac_file (const char *file)
 370 {
 371   int errors;
 372   FILE *in;
 373
 374   in = fopen (file, "r");
 375   if (in == NULL)
 376     {
 377       error (0, errno, "%s", file);
 378       return 1;
 379     }
 380   SET_BINARY (fileno (in));
 381   errors = tac_seekable (fileno (in), file);
 382   if (ferror (in) || fclose (in) == EOF)
 383     {
 384       error (0, errno, "%s", file);
 385       return 1;
 386     }
 387   return errors;
 388 }
 389
 390 #if DONT_UNLINK_WHILE_OPEN
 391
 392 static const char *file_to_remove;
 393 static FILE *fp_to_close;
 394
 395 static void
 396 unlink_tempfile (void)
 397 {
 398   fclose (fp_to_close);
 399   unlink (file_to_remove);
 400 }
 401
 402 static void
 403 record_tempfile (const char *fn, FILE *fp)
 404 {
 405   if (!file_to_remove)
 406     {
 407       file_to_remove = fn;
 408       fp_to_close = fp;
 409       atexit (unlink_tempfile);
 410     }
 411 }
 412
 413 #endif
 414
 415 /* Make a copy of the standard input in `FIXME'. */
 416
 417 static void
 418 save_stdin (FILE **g_tmp, char **g_tempfile)
 419 {
 420   static char *template = NULL;
 421   static char *tempdir;
 422   char *tempfile;
 423   FILE *tmp;
 424   ssize_t bytes_read;
 425   int fd;
 426
 427   if (template == NULL)
 428     {
 429       tempdir = getenv ("TMPDIR");
 430       if (tempdir == NULL)
 431         tempdir = DEFAULT_TMPDIR;
 432       template = xmalloc (strlen (tempdir) + 11);
 433     }
 434   sprintf (template, "%s/tacXXXXXX", tempdir);
 435   tempfile = template;
 436   fd = mkstemp (template);
 437   if (fd == -1)
 438     error (EXIT_FAILURE, errno, "%s", tempfile);
 439
 440   tmp = fdopen (fd, "w+");
 441   if (tmp == NULL)
 442     error (EXIT_FAILURE, errno, "%s", tempfile);
 443
 444 #if DONT_UNLINK_WHILE_OPEN
 445   record_tempfile (tempfile, tmp);
 446 #else
 447   unlink (tempfile);
 448 #endif
 449
 450   while (1)
 451     {
 452       bytes_read = safe_read (STDIN_FILENO, G_buffer, read_size);
 453       if (bytes_read == 0)
 454         break;
 455       if (bytes_read < 0)
 456         error (EXIT_FAILURE, errno, _("stdin: read error"));
 457
 458       /* Don't bother checking for failure inside the loop -- check after.  */
 459       fwrite (G_buffer, 1, bytes_read, tmp);
 460     }
 461
 462   if (ferror (tmp) || fflush (tmp) == EOF)
 463     error (EXIT_FAILURE, errno, "%s", tempfile);
 464
 465   rewind (tmp);
 466
 467   SET_BINARY (fileno (tmp));
 468   *g_tmp = tmp;
 469   *g_tempfile = tempfile;
 470 }
 471
 472 /* Print the standard input in reverse, saving it to temporary
 473    file first if it is a pipe.
 474    Return 0 if ok, 1 if an error occurs. */
 475
 476 static int
 477 tac_stdin (void)
 478 {
 479   int errors;
 480   struct stat stats;
 481
 482   /* No tempfile is needed for "tac < file".
 483      Use fstat instead of checking for errno == ESPIPE because
 484      lseek doesn't work on some special files but doesn't return an
 485      error, either. */
 486   if (fstat (STDIN_FILENO, &stats))
 487     {
 488       error (0, errno, _("standard input"));
 489       return 1;
 490     }
 491
 492   if (S_ISREG (stats.st_mode))
 493     {
 494       errors = tac_seekable (fileno (stdin), _("standard input"));
 495     }
 496   else
 497     {
 498       FILE *tmp_stream;
 499       char *tmp_file;
 500       save_stdin (&tmp_stream, &tmp_file);
 501       errors = tac_seekable (fileno (tmp_stream), tmp_file);
 502     }
 503
 504   return errors;
 505 }
 506
 507 #if 0
 508 /* BUF_END points one byte past the end of the buffer to be searched.  */
 509
 510 static void *
 511 memrchr (const char *buf_start, const char *buf_end, int c)
 512 {
 513   const char *p = buf_end;
 514   while (buf_start <= --p)
 515     {
 516       if (*(const unsigned char *) p == c)
 517         return (void *) p;
 518     }
 519   return NULL;
 520 }
 521
 522 /* FIXME: describe */
 523
 524 static int
 525 tac_mem (const char *buf, size_t n_bytes, FILE *out)
 526 {
 527   const char *nl;
 528   const char *bol;
 529
 530   if (n_bytes == 0)
 531     return 0;
 532
 533   nl = memrchr (buf, buf + n_bytes, '\n');
 534   bol = (nl == NULL ? buf : nl + 1);
 535
 536   /* If the last line of the input file has no terminating newline,
 537      treat it as a special case.  */
 538   if (bol < buf + n_bytes)
 539     {
 540       /* Print out the line from bol to end of input.  */
 541       fwrite (bol, 1, (buf + n_bytes) - bol, out);
 542
 543       /* Add a newline here.  Otherwise, the first and second lines
 544          of output would appear to have been joined.  */
 545       fputc ('\n', out);
 546     }
 547
 548   while ((nl = memrchr (buf, bol - 1, '\n')) != NULL)
 549     {
 550       /* Output the line (which includes a trailing newline)
 551          from NL+1 to BOL-1.  */
 552       fwrite (nl + 1, 1, bol - (nl + 1), out);
 553
 554       bol = nl + 1;
 555     }
 556
 557   /* If there's anything left, output the last line: BUF .. BOL-1.
 558      When the first byte of the input is a newline, there is nothing
 559      left to do here.  */
 560   if (buf < bol)
 561     fwrite (buf, 1, bol - buf, out);
 562
 563   /* FIXME: this is work in progress.... */
 564   return ferror (out);
 565 }
 566
 567 /* FIXME: describe */
 568
 569 static int
 570 tac_stdin_to_mem (void)
 571 {
 572   char *buf = NULL;
 573   size_t bufsiz = 8 * BUFSIZ;
 574   size_t delta = 8 * BUFSIZ;
 575   size_t n_bytes = 0;
 576
 577   while (1)
 578     {
 579       ssize_t bytes_read;
 580       if (buf == NULL)
 581         buf = (char *) malloc (bufsiz);
 582       else
 583         buf = (char *) realloc (buf, bufsiz);
 584
 585       if (buf == NULL)
 586         {
 587           /* Free the buffer and fall back on the code that relies on a
 588              temporary file.  */
 589           free (buf);
 590           /* FIXME */
 591           abort ();
 592         }
 593       bytes_read = safe_read (STDIN_FILENO, buf + n_bytes, bufsiz - n_bytes);
 594       if (bytes_read == 0)
 595         break;
 596       if (bytes_read < 0)
 597         error (EXIT_FAILURE, errno, _("stdin: read error"));
 598       n_bytes += bytes_read;
 599
 600       bufsiz += delta;
 601     }
 602
 603   tac_mem (buf, n_bytes, stdout);
 604
 605   return 0;
 606 }
 607 #endif
 608
 609 int
 610 main (int argc, char **argv)
 611 {
 612   const char *error_message;    /* Return value from re_compile_pattern. */
 613   int optc, errors;
 614   int have_read_stdin = 0;
 615
 616   program_name = argv[0];
 617   setlocale (LC_ALL, "");
 618   bindtextdomain (PACKAGE, LOCALEDIR);
 619   textdomain (PACKAGE);
 620
 621   atexit (close_stdout);
 622
 623   errors = 0;
 624   separator = "\n";
 625   sentinel_length = 1;
 626   separator_ends_record = 1;
 627
 628   while ((optc = getopt_long (argc, argv, "brs:", longopts, NULL)) != -1)
 629     {
 630       switch (optc)
 631         {
 632         case 0:
 633           break;
 634         case 'b':
 635           separator_ends_record = 0;
 636           break;
 637         case 'r':
 638           sentinel_length = 0;
 639           break;
 640         case 's':
 641           separator = optarg;
 642           if (*separator == 0)
 643             error (EXIT_FAILURE, 0, _("separator cannot be empty"));
 644           break;
 645         case_GETOPT_HELP_CHAR;
 646         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 647         default:
 648           usage (1);
 649         }
 650     }
 651
 652   if (sentinel_length == 0)
 653     {
 654       compiled_separator.allocated = 100;
 655       compiled_separator.buffer = (unsigned char *)
 656         xmalloc (compiled_separator.allocated);
 657       compiled_separator.fastmap = xmalloc (256);
 658       compiled_separator.translate = 0;
 659       error_message = re_compile_pattern (separator, strlen (separator),
 660                                           &compiled_separator);
 661       if (error_message)
 662         error (EXIT_FAILURE, 0, "%s", error_message);
 663     }
 664   else
 665     match_length = sentinel_length = strlen (separator);
 666
 667   read_size = INITIAL_READSIZE;
 668   /* A precaution that will probably never be needed. */
 669   while (sentinel_length * 2 >= read_size)
 670     read_size *= 2;
 671   G_buffer_size = read_size * 2 + sentinel_length + 2;
 672   G_buffer = xmalloc (G_buffer_size);
 673   if (sentinel_length)
 674     {
 675       strcpy (G_buffer, separator);
 676       G_buffer += sentinel_length;
 677     }
 678   else
 679     {
 680       ++G_buffer;
 681     }
 682
 683   if (optind == argc)
 684     {
 685       have_read_stdin = 1;
 686       /* We need binary I/O, since `tac' relies
 687          on `lseek' and byte counts.  */
 688       SET_BINARY2 (STDIN_FILENO, STDOUT_FILENO);
 689       errors = tac_stdin ();
 690     }
 691   else
 692     {
 693       for (; optind < argc; ++optind)
 694         {
 695           if (STREQ (argv[optind], "-"))
 696             {
 697               have_read_stdin = 1;
 698               SET_BINARY2 (STDIN_FILENO, STDOUT_FILENO);
 699               errors |= tac_stdin ();
 700             }
 701           else
 702             {
 703               /* Binary output will leave the lines' ends (NL or
 704                  CR/LF) intact when the output is a disk file.
 705                  Writing a file with CR/LF pairs at end of lines in
 706                  text mode has no visible effect on console output,
 707                  since two CRs in a row are just like one CR.  */
 708               SET_BINARY (STDOUT_FILENO);
 709               errors |= tac_file (argv[optind]);
 710             }
 711         }
 712     }
 713
 714   /* Flush the output buffer. */
 715   output ((char *) NULL, (char *) NULL);
 716
 717   if (have_read_stdin && close (0) < 0)
 718     error (EXIT_FAILURE, errno, "-");
 719   exit (errors == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 720 }