src/tac.c

   1 /* tac - concatenate and print files in reverse
   2    Copyright (C) 1988-1991, 1995-2005 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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
  45 #include <regex.h>
  46
  47 #include "error.h"
  48 #include "quote.h"
  49 #include "quotearg.h"
  50 #include "safe-read.h"
  51 #include "unistd-safer.h"
  52
  53 /* The official name of this program (e.g., no `g' prefix).  */
  54 #define PROGRAM_NAME "tac"
  55
  56 #define AUTHORS "Jay Lepreau", "David MacKenzie"
  57
  58 #if defined __MSDOS__ || defined _WIN32
  59 /* Define this to non-zero on systems for which the regular mechanism
  60    (of unlinking an open file and expecting to be able to write, seek
  61    back to the beginning, then reread it) doesn't work.  E.g., on Windows
  62    and DOS systems.  */
  63 # define DONT_UNLINK_WHILE_OPEN 1
  64 #endif
  65
  66
  67 #ifndef DEFAULT_TMPDIR
  68 # define DEFAULT_TMPDIR "/tmp"
  69 #endif
  70
  71 /* The number of bytes per atomic read. */
  72 #define INITIAL_READSIZE 8192
  73
  74 /* The number of bytes per atomic write. */
  75 #define WRITESIZE 8192
  76
  77 /* The name this program was run with. */
  78 char *program_name;
  79
  80 /* The string that separates the records of the file. */
  81 static char *separator;
  82
  83 /* True if we have ever read standard input.  */
  84 static bool have_read_stdin = false;
  85
  86 /* If true, print `separator' along with the record preceding it
  87    in the file; otherwise with the record following it. */
  88 static bool separator_ends_record;
  89
  90 /* 0 if `separator' is to be matched as a regular expression;
  91    otherwise, the length of `separator', used as a sentinel to
  92    stop the search. */
  93 static size_t sentinel_length;
  94
  95 /* The length of a match with `separator'.  If `sentinel_length' is 0,
  96    `match_length' is computed every time a match succeeds;
  97    otherwise, it is simply the length of `separator'. */
  98 static size_t match_length;
  99
 100 /* The input buffer. */
 101 static char *G_buffer;
 102
 103 /* The number of bytes to read at once into `buffer'. */
 104 static size_t read_size;
 105
 106 /* The size of `buffer'.  This is read_size * 2 + sentinel_length + 2.
 107    The extra 2 bytes allow `past_end' to have a value beyond the
 108    end of `G_buffer' and `match_start' to run off the front of `G_buffer'. */
 109 static size_t G_buffer_size;
 110
 111 /* The compiled regular expression representing `separator'. */
 112 static struct re_pattern_buffer compiled_separator;
 113
 114 static struct option const longopts[] =
 115 {
 116   {"before", no_argument, NULL, 'b'},
 117   {"regex", no_argument, NULL, 'r'},
 118   {"separator", required_argument, NULL, 's'},
 119   {GETOPT_HELP_OPTION_DECL},
 120   {GETOPT_VERSION_OPTION_DECL},
 121   {NULL, 0, NULL, 0}
 122 };
 123
 124 void
 125 usage (int status)
 126 {
 127   if (status != EXIT_SUCCESS)
 128     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 129              program_name);
 130   else
 131     {
 132       printf (_("\
 133 Usage: %s [OPTION]... [FILE]...\n\
 134 "),
 135               program_name);
 136       fputs (_("\
 137 Write each FILE to standard output, last line first.\n\
 138 With no FILE, or when FILE is -, read standard input.\n\
 139 \n\
 140 "), stdout);
 141       fputs (_("\
 142 Mandatory arguments to long options are mandatory for short options too.\n\
 143 "), stdout);
 144       fputs (_("\
 145   -b, --before             attach the separator before instead of after\n\
 146   -r, --regex              interpret the separator as a regular expression\n\
 147   -s, --separator=STRING   use STRING as the separator instead of newline\n\
 148 "), stdout);
 149       fputs (HELP_OPTION_DESCRIPTION, stdout);
 150       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 151       printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
 152     }
 153   exit (status);
 154 }
 155
 156 /* Print the characters from START to PAST_END - 1.
 157    If START is NULL, just flush the buffer. */
 158
 159 static void
 160 output (const char *start, const char *past_end)
 161 {
 162   static char buffer[WRITESIZE];
 163   static size_t bytes_in_buffer = 0;
 164   size_t bytes_to_add = past_end - start;
 165   size_t bytes_available = WRITESIZE - bytes_in_buffer;
 166
 167   if (start == 0)
 168     {
 169       fwrite (buffer, 1, bytes_in_buffer, stdout);
 170       bytes_in_buffer = 0;
 171       return;
 172     }
 173
 174   /* Write out as many full buffers as possible. */
 175   while (bytes_to_add >= bytes_available)
 176     {
 177       memcpy (buffer + bytes_in_buffer, start, bytes_available);
 178       bytes_to_add -= bytes_available;
 179       start += bytes_available;
 180       fwrite (buffer, 1, WRITESIZE, stdout);
 181       bytes_in_buffer = 0;
 182       bytes_available = WRITESIZE;
 183     }
 184
 185   memcpy (buffer + bytes_in_buffer, start, bytes_to_add);
 186   bytes_in_buffer += bytes_to_add;
 187 }
 188
 189 /* Print in reverse the file open on descriptor FD for reading FILE.
 190    Return true if successful.  */
 191
 192 static bool
 193 tac_seekable (int input_fd, const char *file)
 194 {
 195   /* Pointer to the location in `G_buffer' where the search for
 196      the next separator will begin. */
 197   char *match_start;
 198
 199   /* Pointer to one past the rightmost character in `G_buffer' that
 200      has not been printed yet. */
 201   char *past_end;
 202
 203   /* Length of the record growing in `G_buffer'. */
 204   size_t saved_record_size;
 205
 206   /* Offset in the file of the next read. */
 207   off_t file_pos;
 208
 209   /* True if `output' has not been called yet for any file.
 210      Only used when the separator is attached to the preceding record. */
 211   bool first_time = true;
 212   char first_char = *separator; /* Speed optimization, non-regexp. */
 213   char *separator1 = separator + 1; /* Speed optimization, non-regexp. */
 214   size_t match_length1 = match_length - 1; /* Speed optimization, non-regexp. */
 215   struct re_registers regs;
 216
 217   /* Find the size of the input file. */
 218   file_pos = lseek (input_fd, (off_t) 0, SEEK_END);
 219   if (file_pos < 1)
 220     return true;                        /* It's an empty file. */
 221
 222   /* Arrange for the first read to lop off enough to leave the rest of the
 223      file a multiple of `read_size'.  Since `read_size' can change, this may
 224      not always hold during the program run, but since it usually will, leave
 225      it here for i/o efficiency (page/sector boundaries and all that).
 226      Note: the efficiency gain has not been verified. */
 227   saved_record_size = file_pos % read_size;
 228   if (saved_record_size == 0)
 229     saved_record_size = read_size;
 230   file_pos -= saved_record_size;
 231   /* `file_pos' now points to the start of the last (probably partial) block
 232      in the input file. */
 233
 234   if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 235     error (0, errno, _("%s: seek failed"), quotearg_colon (file));
 236
 237   if (safe_read (input_fd, G_buffer, saved_record_size) != saved_record_size)
 238     {
 239       error (0, errno, _("%s: read error"), quotearg_colon (file));
 240       return false;
 241     }
 242
 243   match_start = past_end = G_buffer + saved_record_size;
 244   /* For non-regexp search, move past impossible positions for a match. */
 245   if (sentinel_length)
 246     match_start -= match_length1;
 247
 248   for (;;)
 249     {
 250       /* Search backward from `match_start' - 1 to `G_buffer' for a match
 251          with `separator'; for speed, use strncmp if `separator' contains no
 252          metacharacters.
 253          If the match succeeds, set `match_start' to point to the start of
 254          the match and `match_length' to the length of the match.
 255          Otherwise, make `match_start' < `G_buffer'. */
 256       if (sentinel_length == 0)
 257         {
 258           ptrdiff_t i = match_start - G_buffer;
 259           int ret;
 260
 261           if (! (INT_MIN < i && i <= INT_MAX))
 262             error (EXIT_FAILURE, 0, _("record too large"));
 263
 264           ret = re_search (&compiled_separator, G_buffer, i, i - 1, -i, &regs);
 265           if (ret == -1)
 266             match_start = G_buffer - 1;
 267           else if (ret == -2)
 268             {
 269               error (EXIT_FAILURE, 0,
 270                      _("error in regular expression search"));
 271             }
 272           else
 273             {
 274               match_start = G_buffer + regs.start[0];
 275               match_length = regs.end[0] - regs.start[0];
 276             }
 277         }
 278       else
 279         {
 280           /* `match_length' is constant for non-regexp boundaries. */
 281           while (*--match_start != first_char
 282                  || (match_length1 && strncmp (match_start + 1, separator1,
 283                                                match_length1)))
 284             /* Do nothing. */ ;
 285         }
 286
 287       /* Check whether we backed off the front of `G_buffer' without finding
 288          a match for `separator'. */
 289       if (match_start < G_buffer)
 290         {
 291           if (file_pos == 0)
 292             {
 293               /* Hit the beginning of the file; print the remaining record. */
 294               output (G_buffer, past_end);
 295               return true;
 296             }
 297
 298           saved_record_size = past_end - G_buffer;
 299           if (saved_record_size > read_size)
 300             {
 301               /* `G_buffer_size' is about twice `read_size', so since
 302                  we want to read in another `read_size' bytes before
 303                  the data already in `G_buffer', we need to increase
 304                  `G_buffer_size'. */
 305               char *newbuffer;
 306               size_t offset = sentinel_length ? sentinel_length : 1;
 307               ptrdiff_t match_start_offset = match_start - G_buffer;
 308               ptrdiff_t past_end_offset = past_end - G_buffer;
 309               size_t old_G_buffer_size = G_buffer_size;
 310
 311               read_size *= 2;
 312               G_buffer_size = read_size * 2 + sentinel_length + 2;
 313               if (G_buffer_size < old_G_buffer_size)
 314                 xalloc_die ();
 315               newbuffer = xrealloc (G_buffer - offset, G_buffer_size);
 316               newbuffer += offset;
 317               /* Adjust the pointers for the new buffer location.  */
 318               match_start = newbuffer + match_start_offset;
 319               past_end = newbuffer + past_end_offset;
 320               G_buffer = newbuffer;
 321             }
 322
 323           /* Back up to the start of the next bufferfull of the file.  */
 324           if (file_pos >= read_size)
 325             file_pos -= read_size;
 326           else
 327             {
 328               read_size = file_pos;
 329               file_pos = 0;
 330             }
 331           if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 332             error (0, errno, _("%s: seek failed"), quotearg_colon (file));
 333
 334           /* Shift the pending record data right to make room for the new.
 335              The source and destination regions probably overlap.  */
 336           memmove (G_buffer + read_size, G_buffer, saved_record_size);
 337           past_end = G_buffer + read_size + saved_record_size;
 338           /* For non-regexp searches, avoid unneccessary scanning. */
 339           if (sentinel_length)
 340             match_start = G_buffer + read_size;
 341           else
 342             match_start = past_end;
 343
 344           if (safe_read (input_fd, G_buffer, read_size) != read_size)
 345             {
 346               error (0, errno, _("%s: read error"), quotearg_colon (file));
 347               return false;
 348             }
 349         }
 350       else
 351         {
 352           /* Found a match of `separator'. */
 353           if (separator_ends_record)
 354             {
 355               char *match_end = match_start + match_length;
 356
 357               /* If this match of `separator' isn't at the end of the
 358                  file, print the record. */
 359               if (!first_time || match_end != past_end)
 360                 output (match_end, past_end);
 361               past_end = match_end;
 362               first_time = false;
 363             }
 364           else
 365             {
 366               output (match_start, past_end);
 367               past_end = match_start;
 368             }
 369
 370           /* For non-regex matching, we can back up.  */
 371           if (sentinel_length > 0)
 372             match_start -= match_length - 1;
 373         }
 374     }
 375 }
 376
 377 #if DONT_UNLINK_WHILE_OPEN
 378
 379 /* FIXME-someday: remove all of this DONT_UNLINK_WHILE_OPEN junk.
 380    Using atexit like this is wrong, since it can fail
 381    when called e.g. 32 or more times.
 382    But this isn't a big deal, since the code is used only on WOE/DOS
 383    systems, and few people invoke tac on that many nonseekable files.  */
 384
 385 static const char *file_to_remove;
 386 static FILE *fp_to_close;
 387
 388 static void
 389 unlink_tempfile (void)
 390 {
 391   fclose (fp_to_close);
 392   unlink (file_to_remove);
 393 }
 394
 395 static void
 396 record_or_unlink_tempfile (char const *fn, FILE *fp)
 397 {
 398   if (!file_to_remove)
 399     {
 400       file_to_remove = fn;
 401       fp_to_close = fp;
 402       atexit (unlink_tempfile);
 403     }
 404 }
 405
 406 #else
 407
 408 static void
 409 record_or_unlink_tempfile (char const *fn, FILE *fp ATTRIBUTE_UNUSED)
 410 {
 411   unlink (fn);
 412 }
 413
 414 #endif
 415
 416 /* Copy from file descriptor INPUT_FD (corresponding to the named FILE) to
 417    a temporary file, and set *G_TMP and *G_TEMPFILE to the resulting stream
 418    and file name.  Return true if successful.  */
 419
 420 static bool
 421 copy_to_temp (FILE **g_tmp, char **g_tempfile, int input_fd, char const *file)
 422 {
 423   static char *template = NULL;
 424   static char *tempdir;
 425   char *tempfile;
 426   FILE *tmp;
 427   int fd;
 428
 429   if (template == NULL)
 430     {
 431       char const * const Template = "%s/tacXXXXXX";
 432       tempdir = getenv ("TMPDIR");
 433       if (tempdir == NULL)
 434         tempdir = DEFAULT_TMPDIR;
 435
 436       /* Subtract 2 for `%s' and add 1 for the trailing NUL byte.  */
 437       template = xmalloc (strlen (tempdir) + strlen (Template) - 2 + 1);
 438       sprintf (template, Template, tempdir);
 439     }
 440
 441   /* FIXME: there's a small window between a successful mkstemp call
 442      and the unlink that's performed by record_or_unlink_tempfile.
 443      If we're interrupted in that interval, this code fails to remove
 444      the temporary file.  On systems that define DONT_UNLINK_WHILE_OPEN,
 445      the window is much larger -- it extends to the atexit-called
 446      unlink_tempfile.
 447      FIXME: clean up upon fatal signal.  Don't block them, in case
 448      $TMPFILE is a remote file system.  */
 449
 450   tempfile = template;
 451   fd = mkstemp (template);
 452   if (fd < 0)
 453     {
 454       error (0, errno, _("cannot create temporary file %s"), quote (tempfile));
 455       return false;
 456     }
 457
 458   if ((fd = fd_safer (fd)) < 0 || ! (tmp = fdopen (fd, "w+")))
 459     {
 460       error (0, errno, _("cannot open %s for writing"), quote (tempfile));
 461       close (fd);
 462       unlink (tempfile);
 463       return false;
 464     }
 465
 466   record_or_unlink_tempfile (tempfile, tmp);
 467
 468   while (1)
 469     {
 470       size_t bytes_read = safe_read (input_fd, G_buffer, read_size);
 471       if (bytes_read == 0)
 472         break;
 473       if (bytes_read == SAFE_READ_ERROR)
 474         {
 475           error (0, errno, _("%s: read error"), quotearg_colon (file));
 476           goto Fail;
 477         }
 478
 479       if (fwrite (G_buffer, 1, bytes_read, tmp) != bytes_read)
 480         {
 481           error (0, errno, _("%s: write error"), quotearg_colon (tempfile));
 482           goto Fail;
 483         }
 484     }
 485
 486   if (fflush (tmp) != 0)
 487     {
 488       error (0, errno, _("%s: write error"), quotearg_colon (tempfile));
 489       goto Fail;
 490     }
 491
 492   SET_BINARY (fileno (tmp));
 493   *g_tmp = tmp;
 494   *g_tempfile = tempfile;
 495   return true;
 496
 497  Fail:
 498   fclose (tmp);
 499   return false;
 500 }
 501
 502 /* Copy INPUT_FD to a temporary, then tac that file.
 503    Return true if successful.  */
 504
 505 static bool
 506 tac_nonseekable (int input_fd, const char *file)
 507 {
 508   FILE *tmp_stream;
 509   char *tmp_file;
 510   return (copy_to_temp (&tmp_stream, &tmp_file, input_fd, file)
 511           && tac_seekable (fileno (tmp_stream), tmp_file));
 512 }
 513
 514 /* Print FILE in reverse, copying it to a temporary
 515    file first if it is not seekable.
 516    Return true if successful.  */
 517
 518 static bool
 519 tac_file (const char *filename)
 520 {
 521   bool ok;
 522   off_t file_size;
 523   int fd;
 524   bool is_stdin = STREQ (filename, "-");
 525
 526   if (is_stdin)
 527     {
 528       have_read_stdin = true;
 529       fd = STDIN_FILENO;
 530       filename = _("standard input");
 531     }
 532   else
 533     {
 534       fd = open (filename, O_RDONLY);
 535       if (fd < 0)
 536         {
 537           error (0, errno, _("cannot open %s for reading"), quote (filename));
 538           return false;
 539         }
 540     }
 541
 542   /* We need binary I/O, since `tac' relies
 543      on `lseek' and byte counts.
 544
 545      Binary output will leave the lines' ends (NL or
 546      CR/LF) intact when the output is a disk file.
 547      Writing a file with CR/LF pairs at end of lines in
 548      text mode has no visible effect on console output,
 549      since two CRs in a row are just like one CR.  */
 550   SET_BINARY2 (fd, STDOUT_FILENO);
 551
 552   file_size = lseek (fd, (off_t) 0, SEEK_END);
 553
 554   ok = (0 <= file_size
 555         ? tac_seekable (fd, filename)
 556         : tac_nonseekable (fd, filename));
 557
 558   if (!is_stdin && close (fd) != 0)
 559     {
 560       error (0, errno, _("%s: read error"), quotearg_colon (filename));
 561       ok = false;
 562     }
 563   return ok;
 564 }
 565
 566 int
 567 main (int argc, char **argv)
 568 {
 569   const char *error_message;    /* Return value from re_compile_pattern. */
 570   int optc;
 571   bool ok;
 572   size_t half_buffer_size;
 573
 574   /* Initializer for file_list if no file-arguments
 575      were specified on the command line.  */
 576   static char const *const default_file_list[] = {"-", NULL};
 577   char const *const *file;
 578
 579   initialize_main (&argc, &argv);
 580   program_name = argv[0];
 581   setlocale (LC_ALL, "");
 582   bindtextdomain (PACKAGE, LOCALEDIR);
 583   textdomain (PACKAGE);
 584
 585   atexit (close_stdout);
 586
 587   separator = "\n";
 588   sentinel_length = 1;
 589   separator_ends_record = true;
 590
 591   while ((optc = getopt_long (argc, argv, "brs:", longopts, NULL)) != -1)
 592     {
 593       switch (optc)
 594         {
 595         case 'b':
 596           separator_ends_record = false;
 597           break;
 598         case 'r':
 599           sentinel_length = 0;
 600           break;
 601         case 's':
 602           separator = optarg;
 603           if (*separator == 0)
 604             error (EXIT_FAILURE, 0, _("separator cannot be empty"));
 605           break;
 606         case_GETOPT_HELP_CHAR;
 607         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 608         default:
 609           usage (EXIT_FAILURE);
 610         }
 611     }
 612
 613   if (sentinel_length == 0)
 614     {
 615       compiled_separator.allocated = 100;
 616       compiled_separator.buffer = xmalloc (compiled_separator.allocated);
 617       compiled_separator.fastmap = xmalloc (256);
 618       compiled_separator.translate = NULL;
 619       error_message = re_compile_pattern (separator, strlen (separator),
 620                                           &compiled_separator);
 621       if (error_message)
 622         error (EXIT_FAILURE, 0, "%s", error_message);
 623     }
 624   else
 625     match_length = sentinel_length = strlen (separator);
 626
 627   read_size = INITIAL_READSIZE;
 628   while (sentinel_length >= read_size / 2)
 629     {
 630       if (SIZE_MAX / 2 < read_size)
 631         xalloc_die ();
 632       read_size *= 2;
 633     }
 634   half_buffer_size = read_size + sentinel_length + 1;
 635   G_buffer_size = 2 * half_buffer_size;
 636   if (! (read_size < half_buffer_size && half_buffer_size < G_buffer_size))
 637     xalloc_die ();
 638   G_buffer = xmalloc (G_buffer_size);
 639   if (sentinel_length)
 640     {
 641       strcpy (G_buffer, separator);
 642       G_buffer += sentinel_length;
 643     }
 644   else
 645     {
 646       ++G_buffer;
 647     }
 648
 649   file = (optind < argc
 650           ? (char const *const *) &argv[optind]
 651           : default_file_list);
 652
 653   {
 654     size_t i;
 655     ok = true;
 656     for (i = 0; file[i]; ++i)
 657       ok &= tac_file (file[i]);
 658   }
 659
 660   /* Flush the output buffer. */
 661   output ((char *) NULL, (char *) NULL);
 662
 663   if (have_read_stdin && close (STDIN_FILENO) < 0)
 664     error (EXIT_FAILURE, errno, "-");
 665   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 666 }